Five line Java solution with recursion


  • 84
    M
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val == q.val)
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        return false;
    }

  • 0
    P

    it check if statement every loop for 3 times,it's not good.


  • 1
    A

    Why is it not good?


  • 39
    S

    the first 2 lines can be combined into 1 line:
    if (p == NULL || q == NULL) return (p == q);


  • 0
    A

    So what, p==q is also inherently an if condition. This is not saving any extra if's


  • 0
    S

    It is going to save 2 additional operations. "p == q" has one comparison operation. "p == NULL && q == NULL" has 2 comparison operations and one binary operation.


  • 4
    Z

    you can combine the last 3 lines into 1 line:
    return (p.val == q.val) && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);


  • 7
    T
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

  • 0
    M
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 1
    T
    public boolean isSameTree(TreeNode p, TreeNode q) {
        return p == null && q == null || !(p == null || q == null)
            && p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

  • 5
    A
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null) {
            return p == q;
        }
        if (p.val != q.val) {
            return false;
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

  • 0
    B

    public boolean isSameTree(TreeNode p, TreeNode q) {
    return p == null && q == null || !(p == null || q == null) && p.val == q.val && wisdom(p.left, q.left) && wisdom(p.right, q.right);
    }


  • 5
    G

    Here's OP's solution with comments added

    public boolean isSameTree(TreeNode p, TreeNode q) {
        
        // Equal nullity denotes that this branch is the same (local equality)
        // This is a base case, but also handles being given two empty trees
        if (p == null && q == null) return true;
        
        // Unequal nullity denotes that the trees aren't the same
        // Note that we've already ruled out equal nullity above
        else if (p == null || q == null) return false;
            
        // Both nodes have values; descend iff those values are equal
        // "&&" here allows for any difference to overrule a local equality
        if (p.val == q.val) return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        
        // If we're here, both nodes have values, and they're unequal, so the trees aren't the same
        return false;
    }
    

  • 0
        public boolean isSameTree(TreeNode p, TreeNode q) {
          if(p == null && q == null) return true;
          else if(p != null && q != null) {
            boolean b = p.val == q.val;
            b &= isSameTree(p.left, q.left);
            b &= isSameTree(p.right, q.right);
            return b;
          } else return false;
        }

  • 1

    2-line solution:

    if (p == null || q == null) return p == null && q == null;
    return (p.val == q.val) && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    
    

  • 0
    Y

    I would suggest adding if (p == q) return true because if p and q are really the same then it is not necessary to do any further check.

    Also if (p == q) return true will take care of the both null case.


  • 0
    boolean isSameTree(TreeNode p, TreeNode q) {
        return (p == q) || (p != null) && (q != null)
            && (p.val == q.val)
            && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
    

  • 0
    L
     public boolean isSameTree(TreeNode p, TreeNode q) {
            if (p == null || q == null) {
                return p == q;
            }
            return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    

  • 0
    W

    mine is more clear, but I have to say it is not effective!

    public class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            if(p!=null && q!=null){
                if(p.val==q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right)){
                    return true;
                }
            }
            return (p==null && q==null);
        }
    }
    

Log in to reply
 

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