[LintCode/LeetCode] Flatten Binary Tree to Linked

TNFE 发布于2019-08-14 15:12 / 2481人阅读

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;
    }
}

私有云专线服务 binary-tree binary-search-tree Flatten linked

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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