114. Flatten Binary Tree to Linked List(M)

https://leetcode.com/problems/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)?

Solution 1:

我们尝试给出这个函数的定义：

给 flatten 函数输入一个节点 root，那么以 root 为根的二叉树就会被拉平为一条链表。

我们再梳理一下，如何按题目要求把一棵树拉平成一条链表？很简单，以下流程：

1、将 root 的左子树和右子树拉平。

2、将 root 的右子树接到左子树下方，然后将整个左子树作为右子树。

上面三步看起来最难的应该是第一步对吧，如何把 root 的左右子树拉平？其实很简单，按照 flatten 函数的定义，对 root 的左右子树递归调用 flatten 函数即可：

// 定义：将以 root 为根的树拉平为链表
void flatten(TreeNode root) {
    // base case
    if (root == null) return;
    
    flatten(root.left);
    flatten(root.right);

    /**** 后序遍历位置 ****/
    // 1、左右子树已经被拉平成一条链表
    TreeNode left = root.left;
    TreeNode right = root.right;
    
    // 2、将左子树作为右子树
    root.left = null;
    root.right = left;

    // 3、将原先的右子树接到当前右子树的末端
    TreeNode p = root;
    while (p.right != null) {
        p = p.right;
    }
    p.right = right;
}

// 3、将原先的右子树接到当前右子树的末端
   TreeNode p = root;
   while (p.right != null) {
       p = p.right;
   }

这段就是让原右子树接到原左子树的末尾

• 具体到这张图的话, 也就是让5接到4后面

• 如果不用while循环, 则5会直接接到2的后面, 这样点话3和4就丢失

你看，这就是递归的魅力，你说 flatten 函数是怎么把左右子树拉平的？说不清楚，但是只要知道 flatten 的定义如此，相信这个定义，让 root 做它该做的事情，然后 flatten 函数就会按照定义工作。另外注意递归框架是后序遍历，因为我们要先拉平左右子树才能进行后续操作。

Solution 2: (Non-recursive pre-order traversal)

https://www.jiuzhang.com/solution/flatten-binary-tree-to-linked-list/

{
Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    
    while (!stack.empty()) {
        TreeNode node = stack.pop();
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
        
        // connect 
        node.left = null;
        if (stack.empty()) {
            node.right = null;
        } else {
            node.right = stack.peek();
        }
    }

Other Solution:

https://www.jiuzhang.com/solution/flatten-binary-tree-to-linked-list/