剑指offer 86：在二叉树中找到两个节点的最近公共祖先

小半 • 2023年2月3日上午10:54 • 技术随笔 • 阅读 242

剑指offer 86

详细解析：二叉树的最近公共祖先

题目：
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 p和 q，请找到 p 和 q 的最近公共祖先节点。

思路：

自底向上搜索为后序遍历——-回溯算法思想

三种情况：

如果 p 和 q 都在以 root 为根的树中，函数返回的即p 和 q 的最近公共祖先节点 root。
节点本身p，它拥有一个子孙节点q
假设当找到一个节点是p（目标节点）的时候，直接返回当前目标节点，无需再继续递归子树，就算后序找到节点q（子孙节点），则p和q的公共节点还是p ! 所以无需再遍历！
如例中5是4的公共节点，遇到5直接返回5即可，无需再往下遍历到4，计算遍历到4，结果还是5。
那如果 p 和 q 都不在以 root 为根的树中返回 null

本题递归有返回值，因为回溯的过程需要递归函数的返回值做判断

如果搜索整个树，则用变量left、right接住返回值，这个left、right后序还有逻辑处理的需要，也就是后序遍历中处理中间节点的逻辑（也是回溯）。

递归三部曲：

参数已给，返回值为root，这里用辅助函数
终止条件，root为目标节点 p或者 q 或者null,直接返回root !
单层逻辑：后序遍历，通过遍历的结果 left和right进行判断，
如果都不为null即root就是公共祖先（root左右各一个目标节点）！
如果都为null则为返回null ；
如果一方为null，另一方不为null，即不为null的是公共祖先

Java实现：

public class Solution {
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // 自底向上，后序遍历-----回溯
        // 且用left和right记录递归的值
        return check(root,o1,o2).val;
    }
    
    private TreeNode check(TreeNode root, int o1, int o2){
    // 终止条件, 返回目标节点(情况1) or null
        if(root==null || root.val==o1 || root.val==o2){ // ※※※
            return root; // 如果没有遇到目标节点，这个null会一直向上传递
        }
        TreeNode left=check(root.left,o1,o2);
        TreeNode right=check(root.right,o1,o2);
        
        // 利用left和right做判断
        if(left!=null && right!=null){
            return root; // 情况2，即root为公共祖先
        }
        if(left==null && right==null){
            return null;
        }
        if(left==null){
            return right;
        }else{
            return left;
        } // 即不为null的是公共祖先
    }
}