找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 8411|回复: 14
收起左侧

[刷题心得] [leetcode新题] Binary Tree Upside Down

  [复制链接]

5

主题

1

精华

77

积分

资深会员

Rank: 2

积分
77
发表于 11-19-2014 10:27 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 1-14-2015 12:04 PM 编辑

今天看leetcode新题。。Binary Tree Upside Down
需要买书才能看啊 。。。有没有大神已经做了。。贴个题或者啥的!

谢!

发表于 11-19-2014 11:54 PM | 显示全部楼层
Question:
Solution:
At each node you want to assign:
Top down approach:
We need to be very careful when reassigning current node’s left and right children. Besides making a copy of the parent node, you would also need to make a copy of the parent’s right child too. The reason is the current node becomes the parent node in the next iteration.

Difficulty: Medium, Frequency: N/A
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.
p.left = parent.right;
p.right = parent;

public TreeNode UpsideDownBinaryTree(TreeNode root) {
   TreeNode p = root, parent = null, parentRight = null;
   while (p != null) {
      TreeNode left = p.left;
      p.left = parentRight;
      parentRight = p.right;
      p.right = parent;
      parent = p;
p = left; }
   return parent;
}
The above code is actually very similar to the algorithm in reversing a linked list.
60
Bottom up approach:
Although the code for the top-down approach seems concise, it is actually subtle and there are a lot of hidden traps if you are not careful. The other approach is thinking recursively in a bottom-up fashion. If we reassign the bottom-level nodes before the upper ones, we won’t have to make copies and worry about overwriting something. We know the new root will be the left-most leaf node, so we begin the reassignment here.
public TreeNode UpsideDownBinaryTree(TreeNode root) {
   return dfsBottomUp(root, null);
}
private TreeNode dfsBottomUp(TreeNode p, TreeNode parent) {
   if (p == null) return parent;
   TreeNode root = dfsBottomUp(p.left, p);
   p.left = (parent == null) ? parent : parent.right;
   p.right = parent;
   return root;
}
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
回复 支持 5 反对 0

使用道具 举报

20

主题

4

精华

337

积分

高级会员

Rank: 3Rank: 3

积分
337
发表于 11-20-2014 02:29 AM | 显示全部楼层
Thanks cpcs is really fast
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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