Java怎么找二叉树的最近公共祖先

在二叉树中，最近公共祖先（Lowest Common Ancestor, LCA）是指两个节点在树中最近的共同祖先节点。寻找最近公共祖先是二叉树中的一个经典问题，广泛应用于各种算法和数据结构中。本文将详细介绍如何在Java中实现寻找二叉树的最近公共祖先，并探讨不同的解决方案及其优缺点。

1. 问题定义

给定一棵二叉树和两个节点 p 和 q，找到这两个节点的最近公共祖先。最近公共祖先的定义是：在二叉树中，p 和 q 的最低共同祖先节点，且该节点是 p 和 q 的祖先中深度最大的一个。

示例

考虑以下二叉树：

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

• 节点 5 和 1 的最近公共祖先是 3。
• 节点 5 和 4 的最近公共祖先是 5。
• 节点 6 和 2 的最近公共祖先是 5。

2. 解决方案

2.1 递归法

递归法是解决二叉树问题的常用方法。我们可以通过递归遍历二叉树来寻找 p 和 q 的最近公共祖先。

算法步骤

1. 递归终止条件：如果当前节点为 null，或者当前节点就是 p 或 q，则返回当前节点。
2. 递归左右子树：递归地在左子树和右子树中寻找 p 和 q。
3. 判断结果：
   • 如果左子树和右子树都返回非 null 值，说明 p 和 q 分别位于当前节点的左右子树中，当前节点即为最近公共祖先。
   • 如果只有左子树返回非 null 值，说明 p 和 q 都在左子树中，返回左子树的结果。
   • 如果只有右子树返回非 null 值，说明 p 和 q 都在右子树中，返回右子树的结果。

代码实现

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;
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树中的节点数。在最坏情况下，我们需要遍历所有节点。
• 空间复杂度：O(H)，其中 H 是二叉树的高度。递归调用栈的深度取决于树的高度。

2.2 迭代法（使用父指针）

递归法虽然简洁，但在某些情况下可能会导致栈溢出。为了避免这种情况，我们可以使用迭代法来寻找最近公共祖先。

算法步骤

1. 遍历二叉树：使用深度优先搜索（DFS）或广度优先搜索（BFS）遍历二叉树，记录每个节点的父节点。
2. 构建父指针映射：通过遍历，我们可以构建一个从节点到其父节点的映射。
3. 找到 p 的所有祖先：从 p 开始，通过父指针映射向上遍历，记录 p 的所有祖先节点。
4. 找到 q 的最近公共祖先：从 q 开始，通过父指针映射向上遍历，直到找到第一个在 p 的祖先集合中的节点，该节点即为最近公共祖先。

代码实现

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        Set<TreeNode> ancestors = new HashSet<>();
        
        // 遍历二叉树，记录每个节点的父节点
        dfs(root, parent);
        
        // 找到 p 的所有祖先
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }
        
        // 找到 q 的最近公共祖先
        while (q != null) {
            if (ancestors.contains(q)) {
                return q;
            }
            q = parent.get(q);
        }
        
        return null;
    }
    
    private void dfs(TreeNode node, Map<TreeNode, TreeNode> parent) {
        if (node == null) {
            return;
        }
        
        if (node.left != null) {
            parent.put(node.left, node);
            dfs(node.left, parent);
        }
        
        if (node.right != null) {
            parent.put(node.right, node);
            dfs(node.right, parent);
        }
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树中的节点数。我们需要遍历所有节点来构建父指针映射，并且需要遍历 p 和 q 的祖先。
• 空间复杂度：O(N)，我们需要存储每个节点的父节点以及 p 的所有祖先。

2.3 迭代法（不使用父指针）

在某些情况下，我们可能不希望使用额外的空间来存储父指针。我们可以通过迭代法来寻找最近公共祖先，而不需要显式地记录父节点。

算法步骤

1. 使用栈进行遍历：使用栈来模拟递归过程，遍历二叉树。
2. 记录路径：在遍历过程中，记录从根节点到 p 和 q 的路径。
3. 比较路径：找到 p 和 q 的路径中最后一个相同的节点，该节点即为最近公共祖先。

代码实现

import java.util.Stack;

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack = new Stack<>();
        Stack<TreeNode> pathP = new Stack<>();
        Stack<TreeNode> pathQ = new Stack<>();
        
        // 遍历二叉树，记录从根节点到 p 和 q 的路径
        dfs(root, p, q, stack, pathP, pathQ);
        
        // 找到路径中最后一个相同的节点
        TreeNode lca = null;
        while (!pathP.isEmpty() && !pathQ.isEmpty()) {
            TreeNode nodeP = pathP.pop();
            TreeNode nodeQ = pathQ.pop();
            if (nodeP == nodeQ) {
                lca = nodeP;
            } else {
                break;
            }
        }
        
        return lca;
    }
    
    private void dfs(TreeNode node, TreeNode p, TreeNode q, Stack<TreeNode> stack, Stack<TreeNode> pathP, Stack<TreeNode> pathQ) {
        if (node == null) {
            return;
        }
        
        stack.push(node);
        
        if (node == p) {
            pathP.addAll(stack);
        }
        
        if (node == q) {
            pathQ.addAll(stack);
        }
        
        dfs(node.left, p, q, stack, pathP, pathQ);
        dfs(node.right, p, q, stack, pathP, pathQ);
        
        stack.pop();
    }
}

复杂度分析

• 时间复杂度：O(N)，其中 N 是二叉树中的节点数。我们需要遍历所有节点来找到 p 和 q 的路径。
• 空间复杂度：O(H)，其中 H 是二叉树的高度。栈的深度取决于树的高度。

3. 总结

在本文中，我们介绍了三种在Java中寻找二叉树最近公共祖先的方法：递归法、迭代法（使用父指针）和迭代法（不使用父指针）。每种方法都有其优缺点，适用于不同的场景。

• 递归法：代码简洁，易于理解，但在最坏情况下可能会导致栈溢出。
• 迭代法（使用父指针）：避免了递归的栈溢出问题，但需要额外的空间来存储父指针。
• 迭代法（不使用父指针）：不需要额外的空间来存储父指针，但需要记录路径，增加了代码的复杂性。

在实际应用中，可以根据具体需求选择合适的方法。如果二叉树的深度不大，递归法是一个简单而有效的选择。如果二叉树的深度较大，或者需要避免栈溢出问题，可以考虑使用迭代法。