LeetCode日记–114. Flatten Binary Tree to Linked List

发布于 2020-10-07  109 次阅读


碎碎念:好的,昨儿最终还是大半夜吃了锅巴,太罪恶了,太罪恶了。

题目如下:

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

For example, given the following tree:

    3
   / \
  9  20
    /  \
   15   7


The flattened tree should look like:

1
\
2
\
3
\
4
\
5
\
6

这道题的本质就是把二叉树展开成一个链表,且链表的顺序与前序遍历相同。

这里补充一个wiki上面对in place的定义,在狭义的inplace中,要求空间复杂度为O(1),但是在广义的in place中,有O(logn)的额外空间进行辅助排序等操作是允许的。

原文如下:

In-place can have slightly different meanings. In its strictest form, the algorithm can only have a constant amount of extra space, counting everything including function calls and pointers. However, this form is very limited as simply having an index to a length n array requires O(log n) bits. More broadly, in-place means that the algorithm does not use extra space for manipulating the input but may require a small though nonconstant extra space for its operation. Usually, this space is O(log n), though sometimes anything in O(n) is allowed. Note that space complexity also has varied choices in whether or not to count the index lengths as part of the space used. Often, the space complexity is given in terms of the number of indices or pointers needed, ignoring their length. In this article, we refer to total space complexity (DSPACE), counting pointer lengths. Therefore, the space requirements here have an extra log n factor compared to an analysis that ignores the length of indices and pointers.

思路:

方法一:前序遍历

O(n)空间复杂度

因为展开结果顺序和前序遍历结果相同,因此我们很容易想到使用前序遍历进行展开。

但是,因为在前序遍历的过程中如果把子树进行移动则会对遍历的结果造成影响。因此我们先用一个数组把遍历结果存起来,在遍历结束后,再使用数组对树进行展开(记得把左子树变成null)。

代码如下:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> res = new ArrayList<TreeNode>();
        TreeNode curRoot = root;
        helper(curRoot,res);
        for(int i =0;i<res.size() - 1;i++){
            curRoot.right = res.get(i+1);
            curRoot.left = null;
            curRoot = curRoot.right;
        }

    }
    public void helper(TreeNode root, List res){
        if(root==null)
            return ;
        res.add(root);
        helper(root.left,res);
        helper(root.right,res);
    }
}

方法二:找前驱结点

空间复杂度O(1)

刚刚的解法需要存储节点,那么有什么办法可以不存储节点呢?

根据前序遍历,若当前节点的左子树存在,则我们会一直遍历当前节点左孩子的左子树中的节点,再遍历当前节点左孩子的右子树中的节点。那么我们就可以推得,当前节点左孩子的右子树中最右边的节点就是当前节点右子树的前驱结点。

这一段说起来有点绕,可以看一下官方题解中(解法三)的图示

把右子树与左子树中的前驱结点连接上后,就可以把左子树移动到右子树的位置而不怕丢失信息了!

接着再继续往下查找,看移动后的右孩子有无左子树,以此类推,直到完成展开。

迭代实现的代码如下:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        TreeNode cur = root;
        while(cur!=null){
            if(cur.left!=null){
                TreeNode findRIght = cur.left.right;
                if(findRIght!=null){
                while(findRIght.right!=null)
                    findRIght = findRIght.right;
                findRIght.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
                }
                else{
                    cur.left.right = cur.right;
                    cur.right = cur.left;
                    cur.left = null;
                }
            }
            cur = cur.right;
        }
    }
}

递归实现的代码如下:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        TreeNode cur = root;
        while(cur!=null){
            if(cur.left!=null){
                TreeNode findRIght = cur.left.right;
                if(findRIght!=null){
                while(findRIght.right!=null)
                    findRIght = findRIght.right;
                findRIght.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
                }
                else{
                    cur.left.right = cur.right;
                    cur.right = cur.left;
                    cur.left = null;
                }
            }
            cur = cur.right;
        }
    }
}

这个方法也要记得把左子树变为null哦!


你好哇!欢迎来到雷公马碎碎念的地方:)