Lowest Common Ancestor (two nodes are not guaranteed to be in the binary tree )


  • 1
    S

    If the given two nodes are not guaranteed to be in the binary tree, what should the right code be?
    I post my codes here, can anyone point out is it correct?

    (If node one or two is not in the tree, return null)

    public class Solution {
    
    private boolean findOne  = false;
    private boolean findTwo  = false;
    public TreeNode lowestCommonAncestor(TreeNode root,
      TreeNode one, TreeNode two) {
    
    TreeNode result = LCA(root, one, two);
    if(findOne && findTwo){
      return result;
    }
    return null;
    }
    private TreeNode LCA(TreeNode root, TreeNode one, TreeNode two) {
     if(root == null ){
      return root;
    }
    if(root == one){
      findOne = true;
      return root;
    }
    if(root == two){
      findTwo = true;
      return root;
    }
    
    TreeNode leftLCA = LCA(root.left, one, two);
    TreeNode rightLCA = LCA(root.right, one, two);
    
    if(leftLCA != null && rightLCA != null){
      return root;
    }// don't forget this case!!!
    
    return leftLCA != null ?  leftLCA : rightLCA;
    }
    }

  • 2
    S

    I found what's wrong here...
    I used a pre-order traverse the whole tree, but when it came across node "one", it would return "one", and set "findOne" to be true. But if the node "two" is a descendant of node "one", I couldn't find it and "findTwo" is still false. Then the result still be null.
    So now I think I should use post-order traverse the tree.


Log in to reply
 

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