One traverse, and distinguish whether two nodes in the tree


  • 0
    W
    public class Solution {
        boolean flag = false;//whether both of the two are found in this tree
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root==null) return null;
            TreeNode left = lowestCommonAncestor(root.left,p,q);
            if(flag) return left;//the ancestor has been found
            TreeNode right = lowestCommonAncestor(root.right,p,q);
            if(flag) return right;
            if(left!=null&&right!=null){//p and q are in the two different side, so the root is the ancestor
                flag = true;//set the flag true
                return root;
            }else if(root==p||root==q){
                if(left!=null||right!=null||p==q) flag = true;//under this situation, the root must be the ancestor
                return root;
            }else return left!=null?left:right;
        }
    }

  • 0

    That's not O(1) space, it's O(n) space. Recursion management doesn't magically come at no cost.


  • 0
    W

    Thanks for your reminder! I have changed the title.


Log in to reply
 

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