剑指 Offer 68 - II. 二叉树的最近公共祖先

2021年9月14日21:20:25

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//如果pq都在左子树 那么返回左子树返回的值
        if( recur(root.left,p) && recur(root.left,q))
            return lowestCommonAncestor(root.left,p,q);
        else if(recur(root.right,q) && recur(root.right,p ))
            return lowestCommonAncestor(root.right,p,q);
//pq不属于既不都在左子树 也不都在右子树 即 该点是最近的公共祖先
        else return root;


    }
    public boolean recur(TreeNode root, TreeNode p){
        if(root == null && p!=null ) return false;

        if(root == p) return true;
        else return recur(root.left,p) || recur(root.right,p);
    }
}