_236_LowestCommonAncestor.java

import utils.TreeNode;

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

/**
 * @author jzy
 * @GitHub <a href="https://github.com/567jin">567jin</a>
 * @since 2024-03-06 8:46:38
 */
public class _236_LowestCommonAncestor {
    public static void main(String[] args) {
        Integer[] nodes = {3, 5, 1, 6, 2, 0, 8, null, null, 7, 4};
        TreeNode root = TreeNode.genTree(nodes);
        TreeNode p = root.left.left;
        TreeNode q = root.left.right;
        TreeNode node = new _236_LowestCommonAncestor().lowestCommonAncestor(root, p, q);
        System.out.println(node.val);
    }

    /**
     * 遍历的解法  先用一个HashMap存储所有节点的父结点 然后p和q同时向上找 记录各自找到的父结点 如果有重复的则说明有父结点
     */
    private final Map<Integer, TreeNode> parent = new HashMap<>();  // 存储所有节点的父结点
    private final Set<Integer> visited = new HashSet<>();

    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while (p != null) {  // 从p开始往上不断找其所有的父节点并记录下来
            visited.add(p.val);
            p = parent.get(p.val);
        }
        while (q != null) {  // 从q开始不断地找其父结点并判断 是否和p的有重合 如果有则该节点就是最近公共祖先(因为是从下往上找的 因此是最近的 又因为p和q的共同父结点因此是公共祖先)
            if (visited.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }

        return null;

    }

    private void dfs(TreeNode root) {  // 找所有节点的父结点
        if (root == null) {
            return;
        }
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }

    }


    /**
     * 以root为根节点 看看能否找到p和q 如果找到了则返回root
     * 如果只找到一个则
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == root || q == root) {  // 以root为根节点的子树 是否能找到p和q
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null && right == null)
            return null;
        else if (left == null) //
            return right;
        else if (right == null)
            return left;
        else
            return root; // 找到了p q root即是最近公共祖先
    }


}