题解 | #在二叉树中找到两个节点的最近公共祖先#
在二叉树中找到两个节点的最近公共祖先
http://www.nowcoder.com/practice/e0cc33a83afe4530bcec46eba3325116
/*
- function TreeNode(x) {
- this.val = x;
- this.left = null;
- this.right = null;
- } */
/** *
- @param root TreeNode类
- @param o1 int整型
- @param o2 int整型
- @return int整型 */
思路:每个root进递归函数，
先看1.是否有值2.是不是要找的两个节点；
都不是，那就继续找这个root的左、右子树:
左右节点只有其中一个能找到o1或o2，就返回这个左/右节点；
左右节点都能找到，说明这个root就是最近的祖先节点；
都没找到返回null；
function lowestCommonAncestor( root , o1 , o2 ) {
//节点为null，则返回nul
if(!root){
return null
}
//该节点就是o1或o2的位置，就返回root
if(root.val == o1||root.val == o2) return root.val
//不是o1 o2的位置，就继续找root的左右子树
let left = lowestCommonAncestor(root.left,o1,o2);
let right = lowestCommonAncestor(root.right,o1,o2);
//
if(left&&!right){
return left
}
if(right&&!left){
return right
}
if(!right&&!left){
return null
}
return root.val
}
module.exports = {
lowestCommonAncestor : lowestCommonAncestor
};
