114. 二叉树展开为链表

114. 二叉树展开为链表

描述

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例：
给定二叉树 [3,9,20,null,null,15,7]

示例

示例1

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例2

输入：root = []
输出：[]

示例3

输入：root = [0]
输出：[0]

链接

https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/

解题思路

思路一： 后序遍历

1. 将root的左子树和右子树展开；
2. 将root的右子树接到左子树下方，然后将整个左子树作为右子树

实现代码如下：

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    if (root == null) return root;
    flatten(root.left);
    flatten(root.right);

    // 后序遍历位置
    let leftNode = root.left, rightNode = root.right;

    // 将左子树变为右子树
    root.left = null;
    root.right = leftNode;

    // 将原先的右子树接到当前右子树的末端
    let p = root;
    while(p.right != null) {
        p = p.right;
    }
    p.right = rightNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

思路二: 前序遍历和展开同步进行

每次从栈内弹出一个节点作为当前访问的节点，获得该节点的子节点，如果子节点不为空，则依次将右子节点和左子节点压入栈内（注意入栈顺序）。

展开为单链表的做法是，维护上一个访问的节点 prev，每次访问一个节点时，令当前访问的节点为 curr，将 prev 的左子节点设为 null 以及将 prev 的右子节点设为 curr，然后将 curr 赋值给 prev，进入下一个节点的访问，直到遍历结束。需要注意的是，初始时 prev 为 null，只有在 prev 不为 null 时才能对 prev 的左右子节点进行更新

注意：先是右节点入栈

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    if (root == null) return root;
    let stack = [root], prev = null;
    while(stack.length) {
        let curr = stack.pop();
        if (prev !== null) {
            prev.left = null;
            prev.right = curr;
        }
        const left = curr.left, right = curr.right;
        if (right !== null) {
            stack.push(right);
        }
        if (left !== null) {
            stack.push(left);
        }
        prev = curr; 
    }  
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

时间复杂度： O(n) , n 是二叉树的节点数
空间复杂度： O(n)

参考资料

https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solution/er-cha-shu-zhan-kai-wei-lian-biao-by-leetcode-solu/
https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by–26/