题解 | #在二叉树中找到两个节点的最近公共祖先#

方法一（递归）

1.题意整理

• 给定一颗二叉树，以及这个二叉树上两个节点对应的值o1和o2。
• 找到该树中o1、o2节点最近的公共祖先。

2.思路整理

可以试图遍历整颗二叉树，判断以当前节点为根的子树的左右子树上是否包含o1和o2，如果左右子树一边一个，则当前节点就是公共祖先。如果全在左子树，则左子树根节点为公共祖先。如果全在右子树，则右子树根节点为公共祖先。如果都没找到，返回-1。

• 递归终止条件：所有子树遍历之后，都没有找到，直接返回-1。
• 递归如何推进：需要判断当前节点左右子树是否找到了对应节点，如果均不为-1，说明各找到一个，返回当前节点。如果全在左子树，返回left，如果全在右子树，返回right。如果都没有找到，直接返回-1。
• 递归的返回值：返回当前子树是否找到公共祖先。

图解展示：

3.代码实现

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        //树为空，直接返回-1
        if(root==null) return -1;
        //在某个子树上找到o1或o2，返回对应子树的根节点
        if(o1==root.val||o2==root.val) return root.val;
        //当前节点左子树
        int left=lowestCommonAncestor(root.left,o1,o2);
        //当前节点右子树
        int right=lowestCommonAncestor(root.right,o1,o2);
        //均不为-1，说明在当前节点左右子树均找到o1、o2的其中一个，直接返回当前节点值
        if(left!=-1&&right!=-1){
            return root.val;
        }
        //全在左子树上，返回左子树根节点
        else if(left!=-1){
            return left;
        }
        //全在右子树上，返回右子树根节点
        else if(right!=-1){
            return right;
        }
        //没找到，返回-1
        else{
            return -1;
        }
    }
}

4.复杂度分析

• 时间复杂度：需要遍历树中所有节点，所以时间复杂度为$O(n)O(n)$。
• 空间复杂度：最坏情况下，递归栈深度为n，所以空间复杂度是$O(n)O(n)$。