【LeetCode】114.二叉树展开为链表

1 问题

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

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

示例 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]

提示

• 树中结点数在范围 [0, 2000] 内
• -100 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

2 解题思路

2.1 先序遍历

大致思路就是：按照先序遍历的递归方法，将遍历完成的节点列表，再次遍历，将相邻的节点连接起来即可，这里不给出具体实现了。

2.2 迭代

• 如果root左子节点不为空，先标记root.left为next；
• 然后找到next节点的最右侧节点，标记为prev；
• 此时，prev.right指向root.right，就把左右子树连接起来；
• 再将root.right重新指向新的下一个节点，即next；
• 将root.left置为null，继续迭代root.right，此时的root.right其实就是原来的左子树头结点。

详见flatten2方法。

2.3 迭代

原理：

• 按照类似先序遍历的递归思想，先flatten(root.left); 再flatten(root.right);；
• 临时存储root.right，令其指向tmp；
• 将root.right指向新的下一个节点，即指向root.left；
• root.left置为null；
• 找到root的最右侧节点，即原先root.left最右侧的节点，将其指向tmp，即原先root.right.

详见flatten方法。

3 代码

/**
 * 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 flatten2(TreeNode root) {
        //Morris Solution
        if (null == root) {
            return;
        }
        TreeNode curr = root;
        while (null != curr) {
            if (null != curr.left) {
                //the next node is the new right node of curr
                TreeNode next = curr.left;
                TreeNode prev = next;
                //find the rightest node of the left tree
                while (null != prev.right) {
                    prev = prev.right;
                }
                //prev.right points to the root's right
                prev.right = curr.right;
                //root points to the new next, that is curr.left
                curr.right = next;
                curr.left = null;
            }
            //finished the root's left, then traverse the new right
            curr = curr.right;
        }
    }

    public void flatten(TreeNode root) {
        //preorder traversal
        if (null == root) {
            return;
        }
        flatten(root.left);
        flatten(root.right);
        //temporarily store the root.right
        TreeNode tmp = root.right;
        //root.right points to the new next node, root.left
        root.right = root.left;
        root.left = null;
        //find the old left tree's rightest node
        while (null != root.right) {
            root = root.right;
        }
        //then points to the old right tree of root
        root.right = tmp;

    }
}