CONY的世界

114. Flatten Binary Tree to Linked List

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

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

做法是top down，因為tree 走法是preorder traversal ，所以show的順序是root -> left subtree -> right subtree

所以我們要建這個list，可以用reverse preorder traversal 的方式，所以從right subtree先做然後再接上leftsubtree然後再root

做法上要確定兩點，一個就是rightsubtree是否能正確接上left subtree，然後就是left subtree能否正確接上root

首先call flatten (root.right) 後記錄頭prev之後，call flatten(root.left)時，我們recursively下會走到 這個 left subtree‘s rightmost （因為我們先call right 的dfs）後接上之前紀錄的 right subtree的頭，也就是prev

也因此我們確定rightsubtree可以正確接上leftsubtree，接下來就是第二部 確定left subtree能接上root，但這就簡單了

leftsubtree flatten後我們再把頭記錄到prev，然後將他跟root.right相接就完成了

最後回傳root當頭，整個list 就算完成

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