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();
        }
    }

Solution 1:

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

Other Solution: