One traverse O(1) space complexity


  • 0
    W
    public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p==null||q==null) return null;
        TreeNode result = root;
        TreeNode node = root;
        boolean flag = false;
        while(node!=null){
            if(p.val<node.val&&q.val<node.val) node = node.left;//to the left subtree
            else if(p.val>node.val&&q.val>node.val) node = node.right;//to the right subtree
            else{
                result = node;//save the probable result
                for(int i=0;i<2;i++,node=result,p=q){//make sure p and q belong to this tree.
                    while(node!=null){
                        if(p.val<node.val) node = node.left;
                        else if(p.val>node.val) node = node.right;
                        else {
                            flag = true;
                            break;
                        }
                    }
                    if(!flag) return null;//the current p or q is not in this tree
                    flag = false;//continue to make sure q in this tree
                }
                break;
            }
        }
        return result;
    }
    

    }


Log in to reply
 

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