My JAVA bottom-up solution which is easy to understand

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

  • 0

    It's slow, but I like it. Here's a Python version.

    def lowestCommonAncestor(self, root, p, q):
        if root in (None, p, q):
            return root
        left, right = (self.lowestCommonAncestor(kid, p, q)
                       for kid in (root.left, root.right))
        return root if left and right else left or right

Log in to reply

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