算法-二叉树-leetcode.114 二叉树展开为链表 题解

原题如下：leetcode.114 二叉树展开为链表
给你二叉树的根结点 root ，请你将它展开为一个单链表：

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

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

方法1:
通过深度优先遍历，不断将二叉树拉平，

1. 例如上图，通过创建一个数组，不断向头部塞节点，从而实现后序排列，先塞右节点，再塞左节点
2. 遍历是，不断从头部取节点，然后将当前节点，不断拼接在目标节点的尾部
   1. 例如 2 拼接在 1 后面，形成 1 > 2，指针指向 2
   2. 然后 3 拼接在 当前指针后面，指针目前指向 2，所以形成 1 > 2 > 3, 指针指向尾节点 3
   3. 右节点拼接在 当前指针后面，指针指向3，所以 1 > 2 > 3 > 4
   4. 依次类推，完成拼接操作
3. 如果节点有子节点，则重复1，2操作

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    let newNode = new TreeNode(0);
    const result = newNode;

    const list = [];
    if (root) {
        list.push(root);
    }

    while(list.length) {
        const item = list.shift();
        if (item.right) {
            list.unshift(item.right);
        }
        if (item.left) {
            list.unshift(item.left);
        }
        newNode.right = new TreeNode(item.val);
        newNode = newNode.right;
    }

    if (result.right) {
        root.right = result.right.right;
        root.left = null;
    }
};
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
27
28
29
30
31
32
33
34
35
36
37
38

方法2（递归）:

1. 从最左侧的最底部开始向上遍历
2. 将 1 < 2 > 3 -> 2 > 1, (当前节点的左节点，直接替换掉右节点)
3. 从2开始向下查找， 找到1，1没有右节点，将2的旧右节点接在1后面，形成 2 > 1 > 3
4. 这样一个节点就完成了，依次类推
5. 2节点上还有父节点，例如 2 < 5 > 4
6. 需要将左节点2全部拼接在父节点5上，也就是 5 > 2 > 1 > 3
7. 依次向右遍历节点，发现3右侧没有节点，此时将原来5的右节点，拼接在3后面，
8. 即可得到新的树, 5 > 2 > 1 > 3 > 4
9. 依次向上传递，即可获得一个完整的单链表数
10. 此方法，通过递归的形式，从最小节点开始拉平，慢慢拉平到全局，由点辐射到面

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var flatten = function(root) {
    if (!root) return;
    flatten(root.left);
    flatten(root.right);
    // 拉平一个节点
    const right = root.right;
    root.right = root.left;
    root.left = null;

    let p = root;
    while (p.right) {
        p = p.right;
    }
    p.right = right;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19