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

1、解题思路

1. 递归遍历： 从根节点开始递归遍历二叉树。如果当前节点是 o1 或 o2，则返回当前节点。否则，递归遍历左子树和右子树。如果左右子树都返回非空节点，则当前节点是LCA。如果只有一个子树返回非空节点，则返回该节点。
2. 复杂度分析： 时间复杂度：O(n)，每个节点最多访问一次。空间复杂度：O(h)，递归栈的深度为树的高度 h。

2、代码实现

C++

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
        // write code here
        if (root == nullptr) {
            return -1;
        }

        if (root->val == o1 || root->val == o2) {
            return root->val;
        }

        int left = lowestCommonAncestor(root->left, o1, o2);
        int right = lowestCommonAncestor(root->right, o1, o2);

        if (left != -1 && right != -1) {
            return root->val;
        }

        return left != -1 ? left : right;
    }
};

Java

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param o1 int整型
     * @param o2 int整型
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        if (root == null) return -1;

        if (root.val == o1 || root.val == o2) {
            return root.val;
        }

        int left = lowestCommonAncestor(root.left, o1, o2);
        int right = lowestCommonAncestor(root.right, o1, o2);

        if (left != -1 && right != -1) {
            return root.val;
        }

        return left != -1 ? left : right;
    }
}

Python

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @param o1 int整型 
# @param o2 int整型 
# @return int整型
#
class Solution:
    def lowestCommonAncestor(self , root: TreeNode, o1: int, o2: int) -> int:
        # write code here
        if not root:
            return -1
        
        if root.val == o1 or root.val == o2:
            return root.val
        
        left = self.lowestCommonAncestor(root.left, o1, o2)
        right = self.lowestCommonAncestor(root.right, o1, o2)
        
        if left != -1 and right != -1:
            return root.val
        
        return left if left != -1 else right

3、复杂度分析

• 时间复杂度：O(n)，每个节点最多访问一次。
• 空间复杂度：O(h)，递归栈的深度为树的高度 h。