Java O(n) Easy To Understand, Optimal Solution


  • 0
    B

    Explanation
    The idea to this problem is to use a recursive approach. If nodes p and q are NOT identical in value, we return false. Otherwise, we recursively call isSameTree(...) on both their left and right children, and check if they are both true. See code below.

    Time Complexity
    The time complexity is O(n) where n is the number of nodes in the smaller tree between the two inputs, p and q, since we visit the nodes in both trees in sync. If one tree contained more nodes than the other, eventually we would reach the case in which one of p,q would equal null, which returns false.

    class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            /* If both trivially p,q null, return true */
            if (p == null && q == null) {
                return true;
            } 
            // If one of p,q is null OR the values are not equal, return false.
            else if (p == null || q == null || p.val != q.val) {
                return false;
            }
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
    

Log in to reply
 

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