本文系统梳理求二叉树公共祖先问题在lecode上的一些热门题目附完整 Java 代码 + 关键逻辑解析+lecode练习地址。适合 LeetCode 刷题 &面试复习！

1.236二叉树的最近公共祖先

lecode题目：236. 二叉树的最近公共祖先 - 力扣（LeetCode）

思路

• 利用后序遍历“先处理子树，再处理根”的特性
• 通过返回值传递“是否找到目标”的信息
• 在根节点处根据左右子树的返回值判断 公共 位置

实施过程

1.确定递归返回值和参数

• 参数：
  • TreeNode root：当前子树的根
  • TreeNode p, TreeNode q：目标节点
• 返回值：在以 root 为根的子树中，p 和 q 的 公共节点（若只找到一个，则返回该节点；若都没找到，返回 null）

	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)	

2.终止条件

	if (root == null || root == p || root == q) return root;

3.单层递归逻辑
step1：遍历左子树
step2：遍历右子树
step3：处理特殊情况
	- 左有-右空--返回左
	- 左空-右有--返回右
	- 左右空-空

	    TreeNode left=lowestCommonAncestor(root.left, p, q);  
        TreeNode right=lowestCommonAncestor(root.right, p, q);  
        if (left != null && right == null) {//若找到一个节点  
            return left;  
        }else if (left == null && right != null) {//若找到一个节点  
            return right;  
        }else if (left == null && right == null) {//没有找到节点  
            return null;  
        }else {  
            return root;  
        } 

4.最终代码

	class Solution_236 {  
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {  
        if (root == null || root == p || root == q) return root;  
        //后序遍历  
        TreeNode left=lowestCommonAncestor(root.left, p, q);  
        TreeNode right=lowestCommonAncestor(root.right, p, q);  
        if (left != null && right == null) {//若找到一个节点  
            return left;  
        }else if (left == null && right != null) {//若找到一个节点  
            return right;  
        }else if (left == null && right == null) {//没有找到节点  
            return null;  
        }else {  
            return root;  
        }  
  
    }  
}

2.二叉搜索树的最近公共节点

lecode题目：235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

思路

利用搜索树的特性进行剪枝

实施过程

1.确定递归返回值和参数

• 参数：当前根节点 root，目标节点 p、q
• 返回值：p 和 q 的最近公共祖先节点

		public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)

2.终止条件，没有显式的 `if (root == null)` 终止条件？为什么？
当前节点 `root` 的值 介于 `p.val` 和 `q.val` 之间（含等于），即：
p.val <= root.val <= q.val` 或`q.val <= root.val <= p.val`

	return root;

3.单层递归逻辑，利用 BST 有序性剪枝
root.val > p.val && root.val > q.val->p和q都在左子树->递归左子树
root.val < p.val && root.val < q.val->p和q都在右子树->递归右子树
否则p和q分居两侧（或其一等于 root)->当前root就是公共节点

	class Solution_235 {  
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {  
        if(root.val>p.val && root.val>q.val) return lowestCommonAncestor(root.left, p, q);  
        if(root.val<p.val && root.val< q.val) return lowestCommonAncestor(root.right, p, q);  
        return root;  
    }  
}

BST 的 公共节点vs 普通二叉树的公共节点本质区别一句话总结

BST （搜索二叉树）的 公共节点 利用“值的有序性”实现定向搜索；
普通二叉树的 公共节点 因“无序”必须全树遍历 + 信息回溯。