LeetCode 114. Flatten Binary Tree to Linked List

原创

大学里的混子

修改于 2018-10-29 17:10:25

3370

修改于 2018-10-29 17:10:25

文章被收录于专栏：LeetCode

114. Flatten Binary Tree to Linked List


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

    For example, given the following tree:

             1
            / \
           2   5
          / \   \
         3   4   6
    The flattened tree should look like:

            1
             \
              2
               \
                3
                 \
                  4
                   \
                    5
                     \
                      6

关于二叉树的题目，最直接最简单的方法就是采用递归，因为二叉树具有天然的递归结构，实际上二叉树的定义就是用递归的思想来定义的：一个节点的左右子树任然是一个二叉树。

解法一：

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

解法一的思路比较简单，但是要让左子树做flatten后的最后一个节点指向右子树做flatten操作后的第一个节点

，如何得到左子树做flatten后的最后一个节点呢？这就需要一个循环，上述代码中的：

         TreeNode cur = root;
        while (cur.right!=null){
            cur = cur.right;
        }

让cur记录左子树做flatten后的最后一个节点，这样增加了算法的复杂性，效率不是很高。

解法二：

思路：与解法一中的递归思路不一样，我们可以没每找到理论结果中的最后一个节点，再找理论结果中的倒数第二个节点，再倒数第三个………，依次类推，最后找到的是root节点。将写出以下的算法：

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

注意：这里的prev是一个全局变量，prev存的是上一次递归的root的结果。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

其他

登录后参与评论

0 条评论

热度