leetcode114. Flatten Binary Tree to Linked List

zhjx922 發布于2019-08-15 11:07 / 1048人閱讀

摘要：題目要求將一棵二叉樹展開形成一棵鏈表形狀的樹。本質上是將該樹轉變成先序遍歷后的樣子。所以這個例題一步步的操作如下代碼如下思路二遞歸其實這里的思路等價于反轉的先序遍歷。自底向上深度優先遍歷，這要求將前序遍歷的頭結點通過臨時變量保存一下。

題目要求

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / 
       2   5
      /    
     3   4   6
The flattened tree should look like:
   1
    
     2
      
       3
        
         4
          
           5
            
             6
click to show hints.

Hints:
If you notice carefully in the flattened tree, each node"s right child points to the next node of a pre-order traversal.

將一棵二叉樹展開形成一棵鏈表形狀的樹。本質上是將該樹轉變成先序遍歷后的樣子。

思路一：非遞歸

如果我們從圖形的角度來說，每一次都將當前節點的右子樹拼接到左子節點的右子樹下，再將左節點替換原來的右節點。所以這個例題一步步的操作如下：

    1           1           1
   /                       
  2   5           2           2
 /             /            
3   4   6       3   4           3
                                
                      5           4
                                  
                        6           5 
                                     
                                      6

代碼如下：

   public void flatten(TreeNode root) {
        if(root==null) return;
        TreeNode temp = root;
        TreeNode current = root;
        while(current!=null){
            if(current.left!=null){
                temp = current.left;
                while(temp.right!=null) temp = temp.right;
                temp.right = current.right;
                current.right = current.left;
                current.left = null;
                
            }
            current = current.right;
        }
    }

思路二：遞歸

其實這里的思路等價于反轉的先序遍歷。自底向上深度優先遍歷，這要求將前序遍歷的頭結點通過臨時變量保存一下。代碼如下：

    TreeNode pre = null;
    public void flatten2(TreeNode root) {
        if(root==null) return;
        flatten(root.right);
        flatten(root.left);
        root.left = null;
        root.right = pre;
        pre = root;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

云服務器 GPU云服務器 binary-tree binary-search-tree Flatten linked

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/67556.html

[LeetCode] Flatten Binary Tree to Linked List

摘要：思路這題相當于是當的時候，關鍵是要知道要被連接的的前面的一個這樣才可以把接上。用一路做到底，當做到的時候，左邊返回右邊也返回，這時返回自己成為同樣接著繼續做。 Flatten Binary Tree to Linked List Flatten a binary tree to a fake linked list in pre-order traversal.Here we use ...

lowett 2019-08-16 10:34 評論0 收藏0
[Leetcode] Flatten Binary Tree to Linked List 整平二叉

摘要：棧法復雜度時間空間思路對于一個根節點，我們將它的右子樹壓進一個棧中，然后將它的左子樹放到右邊來。如果該節點沒有左子樹，說明該節點是某個左子樹的最后一個節點，我們這時候把棧中最近的右子樹出來接到它的右邊。 Flatten Binary Tree to Linked List Given a binary tree, flatten it to a linked list in-plac...

mikyou 2019-08-14 12:32 評論0 收藏0
[LintCode/LeetCode] Flatten Binary Tree to Linked

Problem Flatten a binary tree to a fake linked list in pre-order traversal.Here we use the right pointer in TreeNode as the next pointer in ListNode. Example 1 1 ...

TNFE 2019-08-14 15:12 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0