[Leetcode] Flatten Binary Tree to Linked List 整平二叉

mikyou 发布于2019-08-14 12:32 / 2367人阅读

摘要：栈法复杂度时间空间思路对于一个根节点，我们将它的右子树压进一个栈中，然后将它的左子树放到右边来。如果该节点没有左子树，说明该节点是某个左子树的最后一个节点，我们这时候把栈中最近的右子树出来接到它的右边。

Flatten Binary Tree to Linked List

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

For example, Given

The flattened tree should look like:

栈法 复杂度

时间 O(N) 空间 O(N)

思路

对于一个根节点，我们将它的右子树压进一个栈中，然后将它的左子树放到右边来。如果该节点没有左子树，说明该节点是某个左子树的最后一个节点，我们这时候把栈中最近的右子树pop出来接到它的右边。

代码

public class Solution {
    public void flatten(TreeNode root) {
        Stack stack = new Stack();
        TreeNode p = root;
        while(p != null || !stack.empty()){
            // 如果有右子树，先压入栈，等待遇到当前节点左子树尽头的时候再pop出来
            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;
            }
            // 移动到下一个待flat节点
            p = p.right;
        }
    }
}

2018/2

class Solution:
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        stack = []
        currentNode = root
        while currentNode is not None:
            if currentNode.right is not None:
                stack.append(currentNode.right)
            if currentNode.left is not None:
                currentNode.right = currentNode.left
                currentNode.left = None
            elif stack:
                currentNode.right = stack.pop()
            currentNode = currentNode.right

2018/10

func flatten(root *TreeNode) {
    if root == nil {
        return
    }
    stack := []*TreeNode{root}
    curr := &TreeNode{0, nil, nil}
    for len(stack) != 0 {
        top := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        // DFS from left to right, push right to the stack first
        if top.Right != nil {
            stack = append(stack, top.Right)
        }
        // push left to the stack
        if top.Left != nil {
            stack = append(stack, top.Left)
        }
        // put top to curr"s right and clear curr"s left
        curr.Left = nil
        curr.Right = top
        // move on to the next
        curr = curr.Right
    }
}

链接左右子树法 复杂度

时间 O(N) 空间 O(1)

思路

如果我们将根节点的右子树接到左子树最后一个节点（就是左子树尽可能靠右下的节点）的右边，那我们可以确定的是，该根节点是已经flat的了。执行完该链接操作，根节点就只有右子树了，这样我们再移动到右子树的根节点，反复执行同样的操作，每次保证一个节点被flat。

代码

public class Solution {
    public void flatten(TreeNode root) {
        while(root != null){
            // 当存在左子树时，说明该节点还没被flat
            if(root.left != null){
                // 找到左子树最后一个节点
                TreeNode endOfLeftSubTree = root.left;
                while(endOfLeftSubTree.right != null){
                    endOfLeftSubTree = endOfLeftSubTree.right;
                }
                // 将右子树加到左子树最后一个节点的右边
                endOfLeftSubTree.right = root.right;
                // 将左子树放到当前节点的右边
                root.right = root.left;
                // 将当前节点左边置空
                root.left = null;
            }
            // 移动到下一个待flat的节点
            root = root.right;
        }
    }
}

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

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

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