在树分支中标记数字的存在背后的基本思想是对数字FOUND使用非空指针,对NOTFOUND使用空指针.
一旦找到数字(p或q),或者根为空,调用堆栈就会回退.后来人们清楚地表明没有搜索到的号码.
有四种可能的情况：
1.)两位父母一方.
root
/ \
Leftsubtree Rightsubtree
p/q q/p
在这种情况下,在下面的代码中,如果(left！= null&& right！= null)返回root,则满足此时将到来;
2.)其他的父母.
q/p p/q
/ OR \
Leftsubtree Rightsubtree
p/q q/p
在这种情况下,如果(root == null || root == p || root == q)返回root,则会满足;
3.)它们中的任何一个都不存在于树中.
这种情况不会被发现.如第2种情况所示,该函数立即返回,无需进一步遍历并在其下方的树中查找其对应项.
4.)树中没有它们.
第一行if(root == null … return;将为每个不存在的子节点执行.最终结果将为null返回,因为找不到任何数字.
逐行代码说明.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) return root;
/* (root == null) This proves that root is not in the branch of tree of our interest. Returning null would means NOTFOUND.*/
/* (root == p || root == q) either p or q or both are found. Returning non-null root would means FOUND. */
/*Check for presence in leftsubtree */
TreeNode left = lowestCommonAncestor(root.left, p, q);
/*Check for presence in rightsubtree */
TreeNode right = lowestCommonAncestor(root.right, p, q);
/* root
/ \
leftsubtree Rightsubtree
p/q q/p
*/
if(left != null && right != null) return root; //both the numbers are found inside tree under root
// left or right subtree OR both don't have p or q. Return the overall find result under root.
return left != null ? left : right;
}
转播
