LeetCode114-二叉树展开为链表

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

中文链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

题目详述

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

1
2
3
4
5
    1
   / \
  2   5
 / \   \
3   4   6

将其展开为：

1
2
3
4
5
6
7
8
9
10
11
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

题目详解

  • 展开左子树。
  • 展开右子树。
  • 把展开后的左子树插入到当前结点和它的右子树之间。
  • 可以进行递归也可以迭代。
  • 每个结点最多被访问两次，时间复杂度为 O(n)。

方法一：递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class LeetCode_00114 {

    // 递归
    public void flatten(TreeNode root) {
        // 终止条件
        if (root == null) {
            return;
        }
        // 展开左子树
        flatten(root.left);
        // 展开右子树
        flatten(root.right);
        // 左子树为空直接返回
        if (root.left == null) {
            return;
        }
        // 将展开后的左子树插入到当前结点与右子树之间
        TreeNode p = root.left;
        while (p.right != null) {
            p = p.right;
        }
        p.right = root.right;
        root.right = root.left;
        root.left = null;
    }
}

方法二：迭代。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode_00114 {

    // 迭代
    public void flatten(TreeNode root) {
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode p = cur.left;
                while (p.right != null) {
                    p = p.right;
                }
                p.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}