Simple and clean Java solution


  • 0
    D
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if ((root == p || root == q) && left == null && right == null) {
            return root;
        } else if (left != null && right != null) {
            return root;
        } else if (left != null || right != null) {
            if (root == p || root == q) {
                return root;
            } else {
                return left != null ? left : right;
            }
        } else {
            return null;
        }
    }
    

    Check if two nodes are inside the tree:

    public static boolean first = false, second = false;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode lca = helper(root, p, q);
        if (first == true && second == true) {
            return lca;
        } else {
            return null;
        }
    }
    
    public TreeNode helper(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if ((root == p || root == q) && left == null && right == null) {
            if (root == p) {
                first = true;
            } else {
                second = true;
            }
            return root;
        } else if (left != null && right != null) {
            return root;
        } else if (left != null || right != null) {
            if (root == p || root == q) {
                if (root == p) {
                    first = true;
                } else {
                    second = true;
                }
                return root;
            } else {
                return left != null ? left : right;
            }
        } else {
            return null;
        }
    }

  • 0
    R

    I believe this does not work if one of the nodes given is not inside the tree, we need first to check both nodes are inside the tree


  • 0
    D

    Yes, you are right. But it is very easy to modify the above code to check whether two nodes are inside tree.


  • 0
    D

    I update my solution. Please check if it is right. Thanks.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.