面试题68 - II. 二叉树的最近公共祖先

image.png

解题思路

非二叉排序树的公共节点，只能用递归，因为非递归必须while
首先明确递归的终止条件，个人感觉，返回值为root的，都是递归终止条件
l=lowestCommonAncestor(root.left,p,q)，l其实就是代表去遍历左子树
一共四种情况，一旦出现==null，就代表该子树，没有p和q（都没有）：
1.如果l==null&&r==null,代表左右子树都找不到p或q，那只能返回null

image.png

2：如果l!=null&&r!=null，代表当前的root就是要找的最近公共祖先节点
如图是找4，5

image.png

3：如果l==null&&r!=null，说明p，q都在右子树，那返回一个右子树

4：同3
从根节点开始只有左子树，所以当left=p或q，就会返回root，这样会出现只有left，而right为null的情况

image.png

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {//非二叉排序树的公共节点，只能用递归，因为非递归必须while，判断
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==p||root==q) return root;//递归的终止条件
        TreeNode l=lowestCommonAncestor(root.left,p,q);
        TreeNode r=lowestCommonAncestor(root.right,p,q);
        if(l==null&&r==null) return null;//判断是否为空
        else if(l!=null&&r!=null) return root;
        else if(l==null&&r!=null) return r;
        else if(l!=null&&r==null) return l;
        return root;
    }
}