一亩三分地论坛

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

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

[Leetcode] LC新题,Binary Tree Up Side Down讨论

[复制链接] |试试Instant~ |关注本帖
JamesJi 发表于 2015-4-14 01:54:09 | 显示全部楼层 |阅读模式

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

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

x
Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.
225645a246ioz5u66s459i.png.thumb.jpg.png

网上也有相应的一些解答但是楼主没有看懂具体的做法。这道题的思路也没有弄太明白。希望大家可以来讨论一下
hwberg 发表于 2015-4-14 02:39:54 | 显示全部楼层

                               
登录/注册后可看大图

你可以这么理解,最终的形态是要把siblings连起来,然后打断右孩子和原parent的连接。
这样就可以写成一个recursion。
  1. public class Solution {
  2.     public TreeNode UpsideDownBinaryTree(TreeNode root) {
  3.         if(root == null)return null;
  4.         if(root.left == null)return root;
  5.         TreeNode newroot = UpsideDownBinaryTree(root.left);
  6.         root.left.left = root.right;
  7.         root.left.right = root;
  8.         root.right = null;
  9.         root.left = null;
  10.         return newroot;

  11.     }
  12. }
复制代码
每次迭代要完成两个任务:
1. bubble up leftmost node,这是新root
2. 连接 siblings, 打断parent与右孩子的连接

回复 支持 1 反对 0

使用道具 举报

372284362 发表于 2015-4-14 07:11:06 | 显示全部楼层
原来是一道需要花钱破解的题。。。题意理解的不确定对不对。。。我觉得是一道用bfs能做的题~不知道tag里有没有这个选项。。。
回复 支持 反对

使用道具 举报

nnno 发表于 2015-4-14 08:25:35 | 显示全部楼层
从树的样子上看,就是最左下的节点变成root,然后删掉所有node到右节点的连接,所有的sibling再连接。
如果把一个node和左右chilrd看成一个三角形,就是把三角形右边的边移除,加上底边,再顺时针旋转60度。
也就是说: 给一个 node, node->left, node->right. 变成node->left->right=node, node->left->left=node->right
剩下的想不出了,能给个更复杂点的example就好了
回复 支持 反对

使用道具 举报

stellari 发表于 2015-4-14 09:08:09 | 显示全部楼层
提示一下:这道题本质上就是一道反转链表题。只是每个node多了一个pointer而已。你只要会反转链表,这道题稍加改进就可以写出来。
回复 支持 反对

使用道具 举报

hwberg 发表于 2015-4-14 10:40:12 | 显示全部楼层

                               
登录/注册后可看大图
重新贴一下图
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-4-14 10:57:21 | 显示全部楼层
hwberg 发表于 2015-4-13 13:39
你可以这么理解,最终的形态是要把siblings连起来,然后打断右孩子和原parent的连接。
这样就可以写成一 ...

谢谢你的解答
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-4-14 10:58:01 | 显示全部楼层
stellari 发表于 2015-4-13 20:08
提示一下:这道题本质上就是一道反转链表题。只是每个node多了一个pointer而已。你只要会反转链表,这道题 ...

对的··刚刚一直还没理解,后来把原来的树歪着看,一下就明白了
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-4-14 10:58:26 | 显示全部楼层
nnno 发表于 2015-4-13 19:25
从树的样子上看,就是最左下的节点变成root,然后删掉所有node到右节点的连接,所有的sibling再连接。
如 ...

对··谢谢你的思路嘿嘿
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-4-14 21:34:50 | 显示全部楼层
贴一下lc的官方解答吧··
  1. public class Solution{
  2.         public TreeNode UpsideDownBinaryTree(TreeNode root){
  3.                 TreeNode p = root;
  4.                 TreeNode parent = null;
  5.                 TreeNode parentRight = null;
  6.                 while(p!= null)
  7.                 {
  8.                         TreeNode left = p.left;
  9.                         p.left = parentRight;
  10.                         parentRight = p.right;
  11.                         p.right = parent;
  12.                         parent = p;
  13.                         p = p.left;
  14.                 }
  15.                 return parent;
  16.         }
  17. }
复制代码
  1. public class Solution{
  2.         public TreeNode UpsideDownBinaryTree(TreeNode root){
  3.                 return dfsBottomUp(root, null);
  4.         }
  5.         private TreeNode dfsBottomUp(TreeNode p, TreeNode parent){
  6.                 if(p == null)
  7.                         return parent;
  8.                 TreeNode root = dfsBottomUp(p.left,p);
  9.                 p.left = (parent == null)?parent:parent.right;
  10.                 p.right = parent;
  11.                 return root;
  12.         }
  13. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-4-15 00:02:51 | 显示全部楼层
上面贴的inplace解法没有看太懂,于是在小伙伴的帮助下,楼主写了一个比较通俗易懂的解法
  1. public class Solution{
  2.         public TreeNode UpsideDownBinaryTree(TreeNode root){
  3.                 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
  4.                 TreeNode newRoot = new TreeNode();
  5.                 if(root == null)
  6.                         return newRoot;
  7.                 ArrayList<Integer> cur = new ArrayList<Integer>();
  8.                 cur.add(root);
  9.                 helper(root, res);
  10.                 res.remove(res.get(res.size()-1));
  11.                 constructTree(res, newRoot);
  12.                 return newRoot;
  13.         }
  14.         private void helper(TreeNode root, ArrayList<ArrayList<Integer>> res)
  15.         {
  16.                 if(root == null)
  17.                         return;
  18.                 ArrayList<Integer> cur = new ArrayList<Integer>();
  19.                 cur.add(root.val);
  20.                 if(root.right != null)
  21.                         cur.add(root.right.val);
  22.                 res.add(cur);
  23.                 helper(root.left, res);
  24.         }
  25.         private void constructTree(ArrayList<ArrayList<Integer>> res, TreeNode newRoot)
  26.         {
  27.                 if(res.size() ==0)
  28.                         return;
  29.                 ArrayList<Integer> cur = res.get(res.size()-1);
  30.                 if(cur.size()>1)
  31.                 {
  32.                         newRoot.left = new TreeNode(cur.get(1));
  33.                         newRoot.right = new TreeNode(cur.get(0));
  34.                 }
  35.                 else newRoot.right = new TreeNode(cur.get(0));
  36.                 res.remove(res.size()-1);
  37.                 constructTree(newRoot.right, res);

  38.         }
  39. }
复制代码
这样应该比较容易读懂了
回复 支持 反对

使用道具 举报

elvisxyu 发表于 2015-4-15 23:51:09 | 显示全部楼层
LC官方解法iterate13行 是不是应该是p=left
否则p在第一次时就成null了吧 而且new个TreeNode left也没在当前循环用到
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-4-16 00:04:29 | 显示全部楼层
elvisxyu 发表于 2015-4-15 10:51
LC官方解法iterate13行 是不是应该是p=left
否则p在第一次时就成null了吧 而且new个TreeNode left也没在当 ...

对··应该是p= left,谢谢指出·
回复 支持 反对

使用道具 举报

lilihao2014 发表于 2015-4-16 00:17:38 | 显示全部楼层
终于找到真人了!!!!
回复 支持 反对

使用道具 举报

 楼主| JamesJi 发表于 2015-4-16 00:19:28 | 显示全部楼层
lilihao2014 发表于 2015-4-15 11:17
终于找到真人了!!!!

大哥的头像老厉害了
回复 支持 反对

使用道具 举报

elvisxyu 发表于 2015-4-16 01:12:46 | 显示全部楼层
JamesJi 发表于 2015-4-16 00:04
对··应该是p= left,谢谢指出·

客气 谢谢共享题目资源
回复 支持 反对

使用道具 举报

elvisxyu 发表于 2015-4-16 01:12:56 | 显示全部楼层
JamesJi 发表于 2015-4-16 00:04
对··应该是p= left,谢谢指出·

客气 谢谢共享题目资源
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 20:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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