二叉树的最近公共祖先

题目要求

给定一个二叉树，以及这个二叉树中的两个节点 p 和 q，要求编写一个函数来寻找并返回这两个节点的最近公共祖先（LCA）。根据定义，二叉树的每个节点都具有一个指向其父节点的引用，最近公共祖先是指在树中最低的节点，同时是 p 和 q 的祖先。需要注意的是，一个节点也可以是它自己的祖先，因此如果 p 是 q 的父节点或者 q 是 p 的父节点，那么 p 或 q 本身就是最近公共祖先。

解题思路

解决这个问题的关键是理解如何在树中寻找两个节点的最近公共祖先。这里有几种方法可以解决这个问题，但最直观的方法是使用递归。以下是解题的步骤：

1. 递归的基本情况：如果当前节点为空或者等于 p 或 q 中的任何一个，那么返回当前节点。这是因为如果找到了 p 或 q，就不需要再继续往下搜索了。

2. 递归搜索：对当前节点的左右子树进行递归调用，分别寻找 p 和 q。

3. 后序遍历：在递归的过程中，我们实际上是在进行后序遍历。首先处理左右子树，然后处理当前节点。

4. 判断逻辑：

   • 如果在左子树中找到了 p 或 q（即左子树递归调用返回非空），并且在右子树中也找到了 p 或 q（即右子树递归调用返回非空），那么当前节点就是 p 和 q 的最近公共祖先。
   • 如果只在左子树找到了 p 或 q，那么返回左子树的结果。
   • 如果只在右子树找到了 p 或 q，那么返回右子树的结果。
   • 如果左右子树都没有找到 p 和 q，那么返回空。

5. 返回结果：递归将结果一层层传递回根节点，最终返回的结果就是 p 和 q 的最近公共祖先。

通过这种方式，我们可以保证在找到 p 和 q 之前，不会提前返回任何节点，从而确保找到的是最近的公共祖先。这个方法的时间复杂度是 O(n)，因为我们需要遍历树中的每个节点。

Golang 版本

package main

import (
	"fmt"
)

// TreeNode is the structure for tree nodes
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// lowestCommonAncestor is the function to find the lowest common ancestor of two nodes p and q
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil || root == p || root == q {
		return root
	}

	left := lowestCommonAncestor(root.Left, p, q)
	right := lowestCommonAncestor(root.Right, p, q)

	if left != nil && right != nil {
		return root
	}

	if left != nil {
		return left
	}

	return right
}

func main() {
	// Example usage:
	// Construct a binary tree here to use the lowestCommonAncestor function.
	// The TreeNode struct and lowestCommonAncestor function assume that the tree and nodes p and q are already defined and passed in as arguments.
	// You would need to create the tree and nodes, then call lowestCommonAncestor with the root and two nodes.
}

这段代码没有包含创建二叉树和节点的部分，因为通常这些信息是由题目给出的，或者需要根据具体情况来构造。在实际使用中，你需要创建一个二叉树的实例，并且提供要查找最近公共祖先的两个节点作为参数来调用lowestCommonAncestor函数。

C++版本

#include <iostream>

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);

        if (left && right) return root;
        return left ? left : right;
    }
};

int main() {
    // Example usage:
    // The TreeNode class and lowestCommonAncestor method assume that the tree and nodes p and q are already defined and passed in as arguments.
    // You would need to create the tree and nodes, then call lowestCommonAncestor with the root and two nodes.
    // TreeNode* root = new TreeNode(3);
    // TreeNode* p = new TreeNode(5);
    // TreeNode* q = new TreeNode(1);
    // Solution solution;
    // TreeNode* lca = solution.lowestCommonAncestor(root, p, q);
    // std::cout << "LCA: " << lca->val << std::endl;
    return 0;
}

这段代码提供了TreeNode结构的定义和Solution类的实现，其中包含了lowestCommonAncestor方法。在main函数中，你需要根据实际情况创建二叉树和节点，并调用lowestCommonAncestor方法。请注意，上面的main函数中的代码是注释掉的示例代码，展示了如何使用这个方法，你需要根据实际的二叉树结构来创建和初始化节点。

Python 版本

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root is None or root == p or root == q:
            return root

        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left and right:
            return root

        return left if left else right

# Example usage:
# if __name__ == "__main__":
#     # Construct the binary tree here
#     root = TreeNode(3)
#     p = TreeNode(5)
#     q = TreeNode(1)
#     # Assume the tree is built and p, q are assigned
#     solution = Solution()
#     lca = solution.lowestCommonAncestor(root, p, q)
#     print(f"LCA: {lca.val}")

这段代码定义了TreeNode类用于表示二叉树的节点，以及Solution类，其中包含了lowestCommonAncestor方法。在实际使用中，你需要创建一个二叉树的实例，并且提供要查找最近公共祖先的两个节点作为参数来调用lowestCommonAncestor方法。注释掉的部分是如何使用这个类的示例。

Java 版本

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    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 root;
        }

        return left != null ? left : right;
    }
}

// Example usage:
// public static void main(String[] args) {
//     TreeNode root = new TreeNode(3);
//     TreeNode p = new TreeNode(5);
//     TreeNode q = new TreeNode(1);
//     Solution solution = new Solution();
//     TreeNode lca = solution.lowestCommonAncestor(root, p, q);
//     System.out.println("LCA: " + lca.val);
// }

这段代码定义了TreeNode类用于表示二叉树的节点，以及Solution类，其中包含了lowestCommonAncestor方法。在实际使用中，你需要创建一个二叉树的实例，并且提供要查找最近公共祖先的两个节点作为参数来调用lowestCommonAncestor方法。注释掉的部分是如何在main方法中使用这个类的示例。

Rust 版本

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

use std::rc::Rc;
use std::cell::RefCell;

pub struct Solution {}

impl Solution {
    pub fn lowest_common_ancestor(
        root: Option<Rc<RefCell<TreeNode>>>,
        p: Option<Rc<RefCell<TreeNode>>>,
        q: Option<Rc<RefCell<TreeNode>>>,
    ) -> Option<Rc<RefCell<TreeNode>>> {
        match (root, p, q) {
            (Some(node), Some(p), Some(q)) => {
                let left = Self::lowest_common_ancestor(node.borrow().left.clone(), Some(p.clone()), Some(q.clone()));
                let right = Self::lowest_common_ancestor(node.borrow().right.clone(), Some(p), Some(q));

                if left.is_some() && right.is_some() {
                    return Some(node);
                }

                left.or(right)
            },
            _ => None,
        }
    }
}

// Example usage:
// fn main() {
//     let root = Some(Rc::new(RefCell::new(TreeNode::new(3))));
//     let p = Some(Rc::new(RefCell::new(TreeNode::new(5))));
//     let q = Some(Rc::new(RefCell::new(TreeNode::new(1))));
//     let lca = Solution::lowest_common_ancestor(root, p, q);
//     println!("LCA: {:?}", lca.map(|node| node.borrow().val));
// }

这段代码定义了TreeNode结构体用于表示二叉树的节点，并使用Rc<RefCell<T>>来处理树的可变共享所有权。Solution结构体包含了lowest_common_ancestor方法，用于查找二叉树中两个节点的最近公共祖先。在实际使用中，你需要创建一个二叉树的实例，并且提供要查找最近公共祖先的两个节点作为参数来调用lowest_common_ancestor方法。注释掉的部分是如何在main函数中使用这个方法的示例。

总结

上述解法采用了递归的方法来寻找二叉树中两个节点的最近公共祖先（LCA）。无论是在 C++、Java 还是 Rust 版本的代码中，核心逻辑都是相同的，只是语法和一些细节上有所不同。以下是解法的关键步骤：

1. 递归的基本情况：如果当前节点为空，或者当前节点等于 p 或 q 中的任何一个，那么返回当前节点。这是因为如果找到了 p 或 q，就不需要再继续往下搜索了。

2. 递归搜索：递归地在左右子树中搜索 p 和 q。调用递归函数lowestCommonAncestor分别对左子树和右子树进行搜索。

3. 后序遍历：在后序遍历的过程中，当左右子树的递归调用都返回非空结果时，意味着在当前节点的两侧各找到了一个节点（p 和 q），因此当前节点就是它们的最近公共祖先。

4. 返回结果：如果左子树或右子树的递归调用返回了一个非空节点，而另一侧返回空，这意味着两个节点都在返回的那一侧。因此，返回非空的那个节点。如果两侧都为空，返回空。

5. 最终结果：递归的最终结果就是最近公共祖先的节点。

这种方法的时间复杂度是 O(n)，其中 n 是树中的节点数，因为最坏的情况下需要遍历整棵树。空间复杂度取决于递归调用栈的深度，最坏情况下是 O(n)（在非平衡树的情况下）。