[LintCode/LeetCode] Flatten Binary Tree to Linked

TNFE 發布于2019-08-14 15:12 / 2601人閱讀

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          2
    /           
   2   5    =>    3
  /              
 3   4   6          4
                     
                      5
                       
                        6

Solution

neat and beautiful

public class Solution {
    public void flatten(TreeNode root) {
        if (root == null) return;
        
        TreeNode left = root.left;
        TreeNode right = root.right;
        flatten(left);
        flatten(right);
        
        root.left = null;
        root.right = left;
        
        TreeNode cur = root;
        while (cur.right != null) cur = cur.right;
        
        cur.right = right;
    }
}

Use stack

    public void flatten(TreeNode root) {
        Stack stack = new Stack();
        TreeNode p = root;
        while(p != null || !stack.empty()){
            if(p.right != null){
                stack.push(p.right);
            }
            if(p.left != null){
                p.right = p.left;
                p.left = null;
            }
            else if(!stack.empty()){
                TreeNode temp = stack.pop();
                p.right=temp;
            }
            p = p.right;
        }
    }

Update 2018-11

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

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

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

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

leetcode114. Flatten Binary Tree to Linked List

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

zhjx922 2019-08-15 11:07 評論0 收藏0
[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] House Robber III

摘要：解法真的非常巧妙，不過這道題里仍要注意兩個細節。中，為時，返回長度為的空數組建立結果數組時，是包括根節點的情況，是不包含根節點的情況。而非按左右子樹來進行劃分的。 Problem The thief has found himself a new place for his thievery again. There is only one entrance to this area,...

macg0406 2019-08-14 15:34 評論0 收藏0
[LintCode/LeetCode] Binary Tree Zigzag Level Orde

Problem Given a binary tree, return the zigzag level order traversal of its nodes values. (ie, from left to right, then right to left for the next level and alternate between). Example Given binary tr...

AlphaGooo 2019-08-14 15:40 評論0 收藏0