二叉树的最近公共祖先 III

/**
 * 思路：
 * 1. 从根节点开始，同时递归查找两个目标节点p和q。
 * 2. 如果找到目标节点或遍历到叶节点，则返回当前节点。
 * 3. 如果左子树和右子树都能找到目标节点，则当前节点即为最近公共祖先。
 * 4. 如果只有一边找到，则返回找到的那边。
 *
 * Definition for a binary tree node.
 * public class Node {
 *     public int val;
 *     public Node left;
 *     public Node right;
 *     public Node parent;
 *     public Node(int x) { val = x; }
 * }
 */
import java.util.HashSet;
import java.util.Set;

public class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        Set<Node> ancestors = new HashSet<>();
        // 从节点p开始追溯其父节点
        while (p != null) {
            ancestors.add(p);
            p = p.parent;
        }
        // 使用stream方法从节点q追溯其父节点
        return Stream.iterate(q, Objects::nonNull, node -> node.parent)
                     .filter(ancestors::contains)
                     .findFirst()
                     .orElse(null); // 找到最近公共祖先或返回null
    }
}