Neighbor Node
出处
Find the immediate right neighbor of the given node, with parent links given, but without root node.
Solution
直接的右邻居(immediate right neighbor)定义为:在给定节点右侧且与给定节点在同一层。由于给定了父指针,故可以利用父指针向上倒推。根据定义,如果当前节点是父节点的右孩子,我们继续倒推,直到当前节点是某个父节点的左孩子,并且该父节点存在右子树。这样,我们立即进入该子树,找到与给定节点处于相同层的最左节点即可。
Complexity
倒推需要复杂度O(h),下降进入子树寻找与给定节点处于相同层的最左节点也需要复杂度O(h),故整体复杂度O(h),h为树高。
Code
Node findDescendent(Node root, int level){
if (root == null) return null;
while (level > 0 && root != null) {
if (root.left != null){
root = root.left;
} else if (root.right != null){
root = root.right;
} else {
root = null;
}
level--;
}
return root;
}
Node rightNeighbor(Node node){
if (node == null) return null;
int level = 0;
Node parent = node.parent;
Node rtn = null;
int flag = 0;
while (parent != null){
if (parent.left == node && parent.right != null){
flag = 1;
}
level++;
node = parent;
parent = parent.parent;
if (flag == 1){
if (parent == null) {
return null;
} else {
rtn = findDescendent(parent, level);
if (rtn != null){
return rtn;
} else {
flag = 0;
}
}
}
}
return null;
}