S**********5
发帖数: 896 | 1 面经上看到的，没什么思路，谁给说说思路和最优能写成什么样？谢谢
Given a binary tree and a leaf node, holding that leaf node and whole tree
falls down such that it is the new root of the tree. Return the modified
tree. |
l*****n
发帖数: 246 | 2 贴个解法：
public void upSideDown(Node root, Node leaf) {
if(root == leaf || root==null){return;}
if(root.left!=null && containsLeaf(root.left, leaf)) {
Node temp = root.left;
root.left = null;
upSideDown(temp, leaf);
temp.right = root;
}
if(root.right!=null && containsLeaf(root.right, leaf)) {
Node temp = root.right;
root.right = null;
upSideDown(temp, leaf);
temp.left = root;
}
}
private boolean containsLeaf(Node root, Node leaf) {
if(root==null){return false;}
if(root==leaf){return true;}
if(containsLeaf(root.left, leaf) || containsLeaf(root.right, leaf)) {
return true;
}
return false;
}
不知题意理解的对不对。我的理解是把整个树从那个leaf node提起来，比如：
1
/ \
2 3
/\ \
4 5 4
从5这个leaf node提起来之后就变成了：
5
/
2
/ \
4 1
\
3
\
4 |
S**********n
发帖数: 22 | 3 1. 先post-traversal，把每次经过的点放在stack里面。比如ls的树，假如5是保留的
leaf，那么先把1放到stack里，再把2放到stack里，4也放到stack里，但4的子节点中
不包含5，所以4最终从stack中去掉。
2.找到5。
3.此时stack里面只有1,2。然后pop出下一个元素2,2作为5的left child。用stack中的
下一个node取代2包含5的那个subtree。
4. 重复3直到stack空 |
s******x
发帖数: 417 | 4 是pre-order吧。。。
【在 S**********n 的大作中提到】
: 1. 先post-traversal，把每次经过的点放在stack里面。比如ls的树，假如5是保留的
: leaf，那么先把1放到stack里，再把2放到stack里，4也放到stack里，但4的子节点中
: 不包含5，所以4最终从stack中去掉。
: 2.找到5。
: 3.此时stack里面只有1,2。然后pop出下一个元素2,2作为5的left child。用stack中的
: 下一个node取代2包含5的那个subtree。
: 4. 重复3直到stack空
|
l*****n
发帖数: 246 | 5 对对，我也觉得是pre
【在 s******x 的大作中提到】
: 是pre-order吧。。。
|
b******i
发帖数: 914 | 6 题目不是很理解，
请问
1
/ \
2 3
/ \
4 5
把5拎起来是很什么样的？答案唯一吗？ |
l****h
发帖数: 1189 | 7 什么叫falls down?有确切定义吗？
叶子作了根，其他node按什么序建树，又有定义吗？
反复各种变种题，不如就把树的几个基本算法弄熟，管他咋变，就那么回事。 |
z***m
发帖数: 1602 | |
g****v
发帖数: 971 | 9 把root到leaf的path找到，然后reverse下就可以了吧。 |
r*g
发帖数: 186 | 10 recursive?
(A)
/ \
(B) (C)
hold (C) and take the rest upside down:
1. trim (B) and (C)
2. hold (A) and take the rest upside down to get (A')
3. add (B) as one child of (A'), (A') as one child of (C)
recur untill (C) is root?
【在 S**********5 的大作中提到】
: 面经上看到的，没什么思路，谁给说说思路和最优能写成什么样？谢谢
: Given a binary tree and a leaf node, holding that leaf node and whole tree
: falls down such that it is the new root of the tree. Return the modified
: tree.
|
r*g
发帖数: 186 | 11 ^^
| |
{ \
{ L_
{
(__________
【在 l*****n 的大作中提到】
: 贴个解法：
: public void upSideDown(Node root, Node leaf) {
: if(root == leaf || root==null){return;}
: if(root.left!=null && containsLeaf(root.left, leaf)) {
: Node temp = root.left;
: root.left = null;
: upSideDown(temp, leaf);
: temp.right = root;
: }
: if(root.right!=null && containsLeaf(root.right, leaf)) {
|
S**********5
发帖数: 896 | 12 WalmartLab的题，我看题目不是很确定是不是lc里的Binary Tree Upside Down 类似，
所以来问问。 |
