一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 583|回复: 10
收起左侧

[Leetcode] Flatten Binary Tree to Linked List 求最简方法

[复制链接] |试试Instant~ |关注本帖
melissami 发表于 2015-7-27 05:13:38 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 melissami 于 2015-7-26 16:15 编辑

原题如下: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,刷提时需要递归的题目非常多,每次都是云里雾里~






CSBrogrammer 发表于 2015-7-27 06:31:15 | 显示全部楼层
  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看看我这个吧,应该挺好理解的
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-27 07:08:54 | 显示全部楼层
文科妹子。。。。。楼主,不容易啊。。。。。。。
回复 支持 反对

使用道具 举报

rfnepku 发表于 2015-7-27 07:39:17 | 显示全部楼层
本帖最后由 rfnepku 于 2015-7-27 07:40 编辑

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

使用道具 举报

stellari 发表于 2015-7-27 16:18:39 | 显示全部楼层
只要是递归,肯定至少用到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

查看全部评分

回复 支持 反对

使用道具 举报

ksqcwyy008 发表于 2015-7-28 01:50:33 | 显示全部楼层
本帖最后由 ksqcwyy008 于 2015-7-28 01:57 编辑
  1. public void flatten(TreeNode root) {
  2.         if(root == null) return;

  3.         if(root.left != null) {
  4.             TreeNode left = root.left;
  5.             TreeNode right = root.right;
  6.             root.left = null;
  7.             root.right = left;
  8.             TreeNode p = left;
  9.             while(p.right != null) {
  10.                 p = p.right;
  11.             }
  12.             p.right = right;
  13.         }
  14.         
  15.         flatten(root.right);
  16.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| melissami 发表于 2015-7-28 09:15:59 | 显示全部楼层
CSBrogrammer 发表于 2015-7-26 17:31
lz看看我这个吧,应该挺好理解的

谢谢你的回复~代码很简洁
能不能稍微解释一下呢?
回复 支持 反对

使用道具 举报

stellari 发表于 2015-7-28 10:58:14 | 显示全部楼层

都写成尾递归的形式了,不如直接转写成循环好了
回复 支持 反对

使用道具 举报

CSBrogrammer 发表于 2015-7-28 11:45:04 | 显示全部楼层
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就好啦。没怎么和人解释过,如果解释不好请见谅
回复 支持 反对

使用道具 举报

AndyLiu0429 发表于 2015-7-28 17:20:50 | 显示全部楼层

  1. public class Solution {
  2.     private TreeNode prev;
  3.     public void flatten(TreeNode root) {
  4.         prev = null;
  5.         helper(root);
  6.     }
  7.    
  8.     private void helper(TreeNode node) {
  9.         if (node == null) {
  10.             return;
  11.         }
  12.         if (prev != null) {
  13.             prev.right = node;
  14.         }
  15.         prev = node;
  16.         TreeNode right = node.right;
  17.         helper(node.left);
  18.         node.left = null;
  19.         helper(right);
  20.     }
  21. }
复制代码
我也来一个,思路就是preorder遍历,同时保留之前遍历的一个节点,用prev表示,然后让prev的right指针指向自己,然后更新preorder的prev指针。接着遍历左边和右边,别忘了把自己的left指针为null
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 11:31

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表