shallowest = curLev;
( `! n+ K' {- u ~. R tempLCA = root;7 M0 z, n) k) ] m6 t# ]. y
}8 G9 e- {0 b* ?
}) Z/ H+ X% n' G# }6 G: \
}% e) \4 T* {0 u% W
}
! ~5 x. K: u8 {9 I8 D
- s# n+ K* g+ ?/ _2 V2 Q! c如果看官能理解我上面的解法。就能看懂我解决多叉树那个原题啦。9 G$ }4 G2 j g
I' j2 _: O1 J* Z& A* N// defination for N-ary TreeNode.
- j g; ?; X G+ v0 Nclass TreeNode{
int val;
ArrayList<TreeNode> children = new ArrayList<TreeNode>();
public TreeNode(int val){
this.val = val;
}
}
5 v. G$ ^+ `7 spublic class MultiTree {
int shallowest = 0; // the shallowest level that I visited in backtracking after I got the first deepest leaf node candidate
int deepest = 0; // the deepest leaf node level
boolean getFirstTarget = false; // whether I got the first deepest leaf node candidate
TreeNode tempLCA; // the node corresponding the shallowest level, which is a LCA candidate
TreeNode LCA; // the result, LCA
0 e, f+ Y& S9 |( A public TreeNode findLCA(TreeNode root){
if(root == null) return root;
dfsFind(root, 0);
return LCA;
}
1 k: y* |7 @( S3 t
public void dfsFind(TreeNode root, int curLev){
if (root.children.isEmpty()) { //get a leaf node
if (!getFirstTarget){ // if hasn't yet get the first deepest leaf node
getFirstTarget = true;
shallowest = curLev;
deepest = curLev;
tempLCA = root;
}
- i5 c* ~$ [- q# R7 g
if (curLev == deepest){ //if current level is the deepest, the candidate LCA might be the result
LCA = tempLCA;
}
: c3 | x5 p0 v( N9 p9 x. w& y if (curLev > deepest){ //if current level is larget than deepeest, reset all the marks
deepest = curLev;
getFirstTarget = false;
shallowest = curLev;
deepest = curLev;
tempLCA = root;
LCA = tempLCA;
}
}
m( C- B, \( r6 X- o, ]- @& H
if (getFirstTarget && curLev <= shallowest) {
shallowest = curLev; //after get the first deepest leaf node candidate, mark the shallowest when backtracking
tempLCA = root;
}
5 Y4 x- @4 a, A# t H: S0 E @ ArrayList<TreeNode> children = root.children;
for (TreeNode child : children){
dfsFind(child, curLev + 1);
if (getFirstTarget && curLev <= shallowest) {
shallowest = curLev; //mark the shallowest when backtracking
tempLCA = root;
}
}
}
}
N+ h& ]9 j( s' V, l& M; ?5 f1 h: O
注释已经写得比较清楚了。我懒得打字解释了,你们画画图就明白了。要是还不明白,我再画画图给你们解释~~
% T" f# ? b* t2 g这家StartUp最近似乎又拿了一轮融资。bar比较高,也是可以理解。我还没有收到他家后续消息。
/ n- Y5 Y# H7 ^8 mAnyaway,在这里发个帖子,求攒人品~~ 也求版主多给些米,我的阅读权限太低,好多帖子看不了。。
5 W2 f; V; \* q( q2 S% {# \: i