讨论/《深度优先搜索》 - 练习:二叉树的最近公共祖先/
《深度优先搜索》 - 练习:二叉树的最近公共祖先
class Solution {
    Map<TreeNode, Boolean> cache = new HashMap<>();
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        if (root.val == p.val || root.val == q.val) {
            return root;
        }
        boolean inLeft = find(root.left, p, q);
        boolean inRight = find(root.right, p, q);
        if (inLeft && inRight) {
            return root;
        }
        if (inLeft) {
            return lowestCommonAncestor(root.left, p, q);
        }
        return lowestCommonAncestor(root.right, p, q);
    }

   // 树 root 里面是否有 p 或者 q 
    boolean find(TreeNode root, TreeNode p, TreeNode q) {
       // 从缓存中获取
        if (cache.containsKey(root)) {
            return (Boolean) cache.get(root);
        }
        if (root == null) {
            return false;
        }
        boolean finded = root.val == p.val || root.val == q.val || find(root.left, p, q) || find(root.right, p, q);
        cache.put(root, finded);
        return finded;
    }
}

// class Solution {
//     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//         if (root == null) {
//             return null;
//         }
//         if (root.val == p.val || root.val == q.val) {
//             return root;
//         }
//         TreeNode tmp1 = lowestCommonAncestor(root.left, p, q);
//         TreeNode tmp2  = lowestCommonAncestor(root.right, p, q);
//         if (tmp1 != null && tmp2 != null) {
//             return root;
//         }
//         if (tmp1 == null) {
//             return tmp2;
//         }
//         return tmp1;
//     }
// }

展开全部 4 讨论