236.二叉树的最近公共祖先

标签: tree, depth-first-search

难度: Medium

通过率: 64.85%

原题链接: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/description/

题目描述

给定一棵二叉树，找到两个指定节点的最近公共祖先（LCA）。根据维基百科中LCA的定义：“最近公共祖先是两节点在树中最低的公共祖先节点（节点允许作为其后代）。”

解题思路

为了解决这个问题，我们可以使用递归的方法来查找树中两个节点的最近公共祖先。基本思想是：

1. 从根节点开始进行深度优先搜索。
2. 如果当前节点是 null，返回 null。如果当前节点是 p 或 q 中的任何一个，则返回当前节点。
3. 递归地在左子树中查找 p 和 q 的最近公共祖先。
4. 递归地在右子树中查找 p 和 q 的最近公共祖先。
5. 如果从左子树中得到了一个非空的结果，说明左子树中找到了至少一个节点 p 或 q；如果从右子树中得到了一个非空的结果，说明右子树中也找到了至少一个节点 p 或 q。
6. 如果左子树和右子树的返回结果都非空，说明当前节点就是 p 和 q 的最近公共祖先。
7. 如果两个子树中只有一个非空返回结果，则该结果就是 p 和 q 的最近公共祖先。

通过这一方法，我们可以有效地找到 p 和 q 在树中的最低公共祖先。同时，递归方法也保证了我们遍历树中每个节点一次，实现了线性时间的复杂度。

代码实现

Python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
    # 如果找到p或q就返回
    if not root or root == p or root == q:
        return root
    
    # 递归查找左子树和右子树
    left = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    
    # 如果左边和右边都有值，说明当前节点是LCA
    if left and right:
        return root
    
    # 否则，返回非空子树中的LCA
    return left if left else right

C++

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        // 如果找到p或q就返回
        if (!root || root == p || root == q)
            return root;
        
        // 递归查找左子树和右子树
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        // 如果左边和右边都有值，说明当前节点是LCA
        if (left && right)
            return root;
        
        // 否则，返回非空子树中的LCA
        return left ? left : right;
    }
};

JavaScript

function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    // 如果找到p或q就返回
    if (!root || root === p || root === q) {
        return root;
    }
    
    // 递归查找左子树和右子树
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    
    // 如果左边和右边都有值，说明当前节点是LCA
    if (left && right) {
        return root;
    }
    
    // 否则，返回非空子树中的LCA
    return left ? left : right;
};

Java

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果找到p或q就返回
        if (root == null || root == p || root == q) {
            return root;
        }
        
        // 递归查找左子树和右子树
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        
        // 如果左边和右边都有值，说明当前节点是LCA
        if (left != null && right != null) {
            return root;
        }
        
        // 否则，返回非空子树中的LCA
        return left != null ? left : right;
    }
}

复杂度分析

时间复杂度：$O(n)$，其中$n$是树中的节点数量。递归遍历每个节点一次。

空间复杂度：$O(n)$，用于递归堆栈。当树为平衡树时，递归深度为 $O( ext{log}n)$，最坏情况下递归深度为 $O(n)$。