[LeetCode] 114. Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a “linked list”:

The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:
Input: root = []
Output: []

Example 3:
Input: root = [0]
Output: [0]

Constraints:
The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

Follow up: Can you flatten the tree in-place (with O(1) extra space)?

二叉树展开为链表。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一 - 迭代

这里我给出迭代的做法，会用到 stack。照着例子看来，最后的输出是按照先序遍历的顺序来的。所以用 stack 先右后左地塞入每个节点，但是在弹出的时候需要注意一些细节，在重连 right 指针的时候，先不要把那个对应的右节点从 stack 中 pop 出来，否则就会出错。具体的参见代码注释。

复杂度

时间O(n)
空间O(n) - stack

代码

Java实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        // corner case
        if (root == null) {
            return;
        }

        // normal case
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
            if (!stack.isEmpty()) {
                // if pop here, the result will be wrong
                // at this step, you get the right node, this node will be poped out in the next round
                cur.right = stack.peek();
            }
            cur.left = null;
        }
    }
}

JavaScript实现

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

    // normal case
    let stack = [];
    stack.push(root);
    while (stack.length) {
        let cur = stack.pop();
        if (cur.right != null) {
            stack.push(cur.right);
        }
        if (cur.left != null) {
            stack.push(cur.left);
        }
        if (stack.length) {
            cur.right = stack[stack.length - 1];
        }
        cur.left = null;
    }
};

思路二 - 也是迭代，无需额外空间

参考这个帖子的解法一。

复杂度

时间O(n)
空间O(n) - stack

代码

Java实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        while (root != null) {
            // 如果左子树为空，直接去看右子树
            if (root.left == null) {
                root = root.right;
            } else {
                // 找到左子树的最右孩子，走到4的位置
                TreeNode pre = root.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                // 把左子树的最右孩子连接到右子树
                pre.right = root.right;        // 4 - 5
                root.right = root.left;        // 1 - 2，只是2从1的左孩子变成了右孩子
                root.left = null;            // 1的左指针设置为NULL
                root = root.right;            // 1走到2
            }
        }
    }
}

[LeetCode] 114. Flatten Binary Tree to Linked List

思路一 - 迭代

复杂度

代码

思路二 - 也是迭代，无需额外空间

复杂度

代码

相关题目