Flatten Binary Tree to Linked List 求最简方法

原题如下：https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
Given a binary tree, flatten it to a linked list in-place.
已经对这这道题，纠结了一整天了，无果。。。作为一个文科出身妹子想刷刷题容易么来这里寻求万能的坛友帮助~~

第一反应，这道题是in place preorder traversal
最直观的解法preorder the tree, and put the result in a linkedlist, and then loop through the linkedlist to add it to the tree but this O(n) extra space
原题要求inplace，所以上述方法不能用


然后在网上找了很多别人的算法，大体上来说有两种写法，一个是用recursion，另外是用iteration，但是都觉得很复杂，很难理解，对recursion一直感到非常无力。

找到了下面两个recursion的写法
http://n00tc0d3r.blogspot.com/2013/03/flatten-binary-tree-to-linked-list-in.html

1. public TreeNode flatten(TreeNode root) {  
   
2.    if (root == null) return root;  
   
3.    TreeNode rtree = root.right;  
   
4.    if (root.left != null) {  
   
5.      root.right = root.left;  
   
6.      root.left = null;  
   
7.      root = flatten(root.right);  
   
8.    }  
   
9.    if (rtree != null) {  
   
10.      root.right = rtree;  
    
11.      root = flatten(root.right);  
    
12.    }  
    
13.    return root;  
    
14. }  

复制代码

每次自己一步一步推理的时候，到了root = flatten(root.right); 再次递归调用flatten的时候就乱了/(ㄒoㄒ)/~~


另一个recursion
http://jane4532.blogspot.com/2013/07/flatten-binary-tree-to-linked.html

1. class Solution {
   
2. public:
   
3.     void build(TreeNode *root, TreeNode *&tmp)
   
4.     {
   
5.         if(root)
   
6.         {
   
7.             build(root->right, tmp);
   
8.             build(root->left, tmp);
   
9.             
   
10.             root->right=tmp;
    
11.             tmp=root;
    
12.             root->left=NULL;
    
13.         }
    
14.     }
    
15.     void flatten(TreeNode *root) {
    
16.         // Start typing your C/C++ solution below
    
17.         // DO NOT write int main() function
    
18.         TreeNode *tmp=NULL;
    
19.         build(root, tmp);
    
20.         
    
21.     }
    
22. };

复制代码

代码非常简洁，但实际上很难理解，执行了两次build之后结果是什么，tmp表示什么，都不明白~~(>_<)~~


有没有好心人帮忙解释一下，或者自己有更好的解法（对学弱来说，最简的方法不一定是代码最少或者时间复杂度空间复杂度最小，主要是满足题目条件的情况下最容易理解的）

顺便求大神解释一下recursion，刷提时需要递归的题目非常多，每次都是云里雾里~

1. public void flatten(TreeNode root) {
   
2.         TreeNode[] buddyOnTop = new TreeNode[1];
   
3.         flatten(root, buddyOnTop);
   
4.     }
   
5.    
   
6.     private void flatten(TreeNode root, TreeNode[] buddyOnTop) {
   
7.         if(root == null) return;
   
8.         
   
9.         TreeNode curRight = root.right;
   
10.         
    
11.         if(buddyOnTop[0] != null) {
    
12.             buddyOnTop[0].left = null;
    
13.             buddyOnTop[0].right = root;
    
14.         }
    
15.         
    
16.         buddyOnTop[0] = root;
    
17.         flatten(root.left, buddyOnTop);
    
18.         flatten(curRight, buddyOnTop);
    
19.     }

复制代码

lz看看我这个吧，应该挺好理解的

文科妹子。。。。。楼主，不容易啊。。。。。。。

第一种方法就是把左子树A整个接到root的右边，然后对左子树A重复调用flattern直到把它变linkedlis。 然后在接上的左子树A的最底层right child之后再接上原先的root的整个右子树B, 这个时候B还不是linkedlist，对B再进行重复调用flattern把它变成linkedlist。。个人理解，仅供参考哈。。

只要是递归，肯定至少用到O(递归深度)级别的内存。所以严格来讲，这题真要O(1)内存的话，连递归也不应该用。不过咱们还是讨论下递归算法：

这道题的递归思路其实很简单：
1. Flatten左子树，2. Flatten右子树，3. 把Flatten的右子数加到左子树的后面去。

但是难点在于，要完成步骤3，则必须知道左子树Flatten后的最后一个节点是什么。

所以，我们的递归函数flatten要做到：
输入：待Flatten的子树的root
输出：Flatten后的子树的最后一个节点。

可能出现五种情况：

1. root是Null？返回Null
2. root没有左右子树？返回自身。
3. root有右子树，但是没有左子树？把Flatten的右子树拼接到root.right上，而不是左子树的最后一个节点上。
返回右子树的最后一个节点。
4. root有左子树，但是没有右子树？把Flatten的左子树拼接到root.right上即可。返回左子树的最后一个节点。
5. root有左右子树？这是最正常的情况，把左右两子树各自Flatten，然后把右子树拼接到左子树的最后一个节点。返回右子树的最后一个节点。

你的第一段代码，就是用一种相对简洁的方式，实现了上面说的5种不同情况的判断。我如何知道第一段代码对? 你可以将这五种情况逐一代入到flatten函数中去，看它是不是真的做到了我们希望他做的事情。首先第1,2种情况是Base Case，很容易验证这两种情况下是正确的；再来看情况3. root.left = NULL, root.right != NULL。所以此时第一段if不会被执行，而第二段会，所以：右侧的子树会被flatten，并且是直接挂在root.right上的。最后返回的是更新过的root，而这个更新过的root是从flatten(root.right)获得的。如果“flatten(root.right)”返回的是root.right的最后一个值”，那么现在root=flatten(root.right)肯定也是正确的。
4,5两种情况也可以按照类似的方法分析。

这就是数学归纳法：如果第1步是正确的；当第N-1步正确时，第N步也是正确的。那么任何步上都一定是正确的。因此第一种代码必然正确。

第二种代码换了个思路：它的build的意思：“建立好root及其之后的那部分Flattened list”，因此，它的工作是。

1. flatten root.right及其以后的部分。（此时返回右子树的根tmp）
2. flatten root.left及其以后的部分。因为最后的List一定是root->root.left->....->root.right->...的形式，所以我们只要flatten root.left所在的子树，然后把已经flatten好的root.right挂接到其后面即可。（此时返回左子树的根tmp）。
3. 把左子树的跟挂接到root.right即可。

1. public void flatten(TreeNode root) {
   
2.         if(root == null) return;
   
3. 
   
4.         if(root.left != null) {
   
5.             TreeNode left = root.left;
   
6.             TreeNode right = root.right;
   
7.             root.left = null;
   
8.             root.right = left;
   
9.             TreeNode p = left;
   
10.             while(p.right != null) {
    
11.                 p = p.right;
    
12.             }
    
13.             p.right = right;
    
14.         }
    
15.         
    
16.         flatten(root.right);
    
17.     }

复制代码

CSBrogrammer 发表于 2015-7-26 17:31
lz看看我这个吧，应该挺好理解的

谢谢你的回复~代码很简洁
能不能稍微解释一下呢？

ksqcwyy008 发表于 2015-7-28 01:50

都写成尾递归的形式了，不如直接转写成循环好了

melissami 发表于 2015-7-28 09:15
谢谢你的回复~代码很简洁
能不能稍微解释一下呢？

谢谢。大概意思是用TreeNode[]来keep track and update上一层的node，这样每进入到下一层我们会有一个pointer指向该层被flatten后应该指向的上层node。同时因为我们更新了上一层node的right child，在从上一层进入到该层前我们需要保存上一层原本的right child。因此请注意，line 17进入到line 18的时候buddyOnTop[0]是很有可能被改变的。最后follow recursion top down manner就好啦。没怎么和人解释过，如果解释不好请见谅

1. 
   
2. public class Solution {
   
3.     private TreeNode prev;
   
4.     public void flatten(TreeNode root) {
   
5.         prev = null;
   
6.         helper(root);
   
7.     }
   
8.    
   
9.     private void helper(TreeNode node) {
   
10.         if (node == null) {
    
11.             return;
    
12.         }
    
13.         if (prev != null) {
    
14.             prev.right = node;
    
15.         }
    
16.         prev = node;
    
17.         TreeNode right = node.right;
    
18.         helper(node.left);
    
19.         node.left = null;
    
20.         helper(right);
    
21.     }
    
22. }

复制代码

我也来一个，思路就是preorder遍历，同时保留之前遍历的一个节点，用prev表示，然后让prev的right指针指向自己，然后更新preorder的prev指针。接着遍历左边和右边，别忘了把自己的left指针为null