长大后想做什么？做回小孩！

0%

LeetCode——二叉树展开为链表

发表于 分类于 Valine：
本文字数： 643

NO.114 二叉树展开为链表 中等

Jmiuiq.png

思路一：前序遍历 观察示例，发现展开后的链表是二叉树的前序遍历序列。

可以先前序遍历获得遍历序列，然后将序列依次连接到根的右节点上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void flatten(TreeNode root) {
    if (root==null)return;
    //前序遍历序列
    LinkedList<TreeNode> list=new LinkedList<>();
    preorder(list,root);
    //开始展开为链表
    TreeNode p = list.removeFirst();
    p.left=null;
    while (list.size() > 0) {
        TreeNode temp = list.removeFirst();
        temp.left=null;
        p.right=temp;
        p=p.right;
    }
}

private void preorder(LinkedList<TreeNode> list, TreeNode root) {
    if (root==null)return;
    list.add(root);
    preorder(list,root.left);
    preorder(list,root.right);
}

时间复杂度：O(n) 空间复杂度：O(n)不符合要求

思路二：原地修改指向 依然是观察示例，得到一个大概的思路把靠右的元素先连接到左子树的最右节点上，然后把整个左子树覆盖到之前靠右的元素位置。这样多次进行，从而把一个二叉树”捋顺”，即所有的节点都移到最右边。看下面例子，结合代码很好理解。

JnwGUe.png

如果curr的左子树不为空，找到左子树的最右节点p，将p的右指针指向curr的左子树，如下图：

Jnw8ED.png

(这是是个示意图，实际结构中curr右指针依然指向3节点)，然后将curr的右指针指向curr的左子树，并将curr的左指针置空。

Jnw1HO.png

移动curr指针，然后像之前一样curr的左子树不为空，curr左子树的最右节点为p，p的右指针指向curr的右子树。

JnwlDK.png

重复第二步，curr的右指针指向curr的左子树，curr的左指针置空。

JnwKjx.png

继续向右深搜移动curr，找到下一个左指针不为空的节点。

JnwQu6.png

curr的左子树的最右节点为p，p的右指针指向curr的右子树。

JnwJ4H.png

curr的右指针指向curr的左子树，curr的左指针置空。

继续向右深搜移动curr寻找左指针不为空的节点，curr为空，展开完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void flatten(TreeNode root) {
    TreeNode curr=root;
    while (curr != null) {
        //找到左子树不为空的节点
        if (curr.left != null) {
            //p指向左子树的最右节点
            TreeNode p = curr.left;
            while(p.right!=null)p=p.right;
            //把curr的左子树移动到curr的右子树
            p.right=curr.right;
            curr.right=curr.left;
            curr.left=null;
        }
        //移动curr
        curr=curr.right;
    }
}

时间复杂度：O(n) 最坏情况二叉树初始就是链表形式，但是全部都是靠左，curr需要遍历每个节点。

空间复杂度：O(1)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github