LeetCode 114. Flatten Binary Tree to Linked List

[Woodyiiiiiii]

Given a binary tree, flatten it to a linked list in-place.

For example, given the following tree:

    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

---

仔细观察，将二叉树变为链表的顺序是按照二叉树先序遍历的顺序。

最简单的方法，就是先序遍历一次二叉树，按顺序将节点存储进list中，然后再次重建二叉树，依次取出节点连接到右孩子节点。

// preOrder
class Solution {
    public void flatten(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return;
        }
        LinkedList<TreeNode> list = new LinkedList<>();
        preOrder(root, list);
        while (root != null && !list.isEmpty()) {
            root.left = null;
            root.right = list.pollFirst();
            root = root.right;
        }
    }
    void preOrder(TreeNode node, LinkedList<TreeNode> list) {
        if (node != null) {
            list.add(node);
            preOrder(node.left, list);
            preOrder(node.right, list);
        }
    }
}

那么难点在于如何原地调正二叉树位置使其变成符合先序顺序的单链表。

关键在于要把右子树节点连接到左子树最右边，相当于允许先序遍历的末尾，然后把左子树的先序遍历的下一个节点连接到右子树中。我们使用 镜像(Mirror) 解法，先把左子树和右子树节点互换，这样单链表的下一个节点就摆好位置了，接着把左子树(原右子树)部分连接到该确认节点的最右边，断开连接。

// mirror approach
class Solution {
    public void flatten(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return;
        }
        TreeNode rLeft, rRight, tmp;
        while (root != null) {
            rLeft = root.left;
            rRight = root.right;
            root.left = rRight;
            root.right = rLeft;
            tmp = root;
            while (tmp.right != null) {
                tmp = tmp.right;
            }
            tmp.right = root.left;
            root.left = null;
            root = root.right;
        }
    }
}

更多解法可以查阅参考资料2和3。

---

参考资料：

• https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
• https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/683792/Java-Beats-100
• [LeetCode] 114. Flatten Binary Tree to Linked List grandyang/leetcode#114