二叉树查找最近公共父节点

发表于 | 分类于

题目

查询二叉树中两个节点的最近公共父节点

思路

递归查找，具体看注释

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// function Node(x){
//     this.val=x;
//     this.left=null;
//     this.right=null;
// }//定义节点结构

function parent(root,a,b){
    if(root==null) return null;//如果根节点为空则返回空
    if(root==a||root==b)  return root;//如果a，b之中有一个是根节点，则返回根节点
    
    
    var left=parent(root.left,a,b);
    var right=parent(root.right,a,b);//递归左右子树的结果
    if(left&&right){
        return root;//如果a,b分别在左右子树上，则最近的公共节点是root
    }
    return left?left:right;//不为空的那个是公共父节点
}