二叉树的最近公共祖先 II

/*
 * Leetcode 1644: Lowest Common Ancestor of a Binary Tree II using Java Streams
 * 
 * 思路：
 * 使用流的方式不适合解决树的递归问题，因为流更适合处理集合，而树的结构要求递归处理。此处依然使用递归方法，只是展示如何在树的遍历过程中使用流处理集合。
 */

public class Solution {
    private boolean foundP = false;
    private boolean foundQ = false;
    
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode lca = findLCA(root, p, q);
        if (foundP && foundQ) {
            return lca;
        }
        return null;
    }
    
    private TreeNode findLCA(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        TreeNode left = findLCA(root.left, p, q);
        TreeNode right = findLCA(root.right, p, q);
        if (root == p) {
            foundP = true;
            return root;
        }
        if (root == q) {
            foundQ = true;
            return root;
        }
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }
}

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