0100. Same Tree

Easy | Tree | 20 ms (98.94%), 14.3 MB (59.78%)

❓ Problem Statement

Source: LeetCode - Same Tree GitHub: Solution / Performance

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

✍🏻 Constraints & Example

Constraints:

• The number of nodes in both trees is in the range [0, 100].

• -10^4 <= Node.val <= 10^4

💡 Ideas

We could check two trees are identical by different kinds of traversal. For here, we use pre-order traversal.

Instead of iterating two trees separately, we could traverse two trees simultaneously. However, we should take care of the existence of child nodes while traversing.

• If two nodes popped from the stack are both null, skip the current iteration.

• If one of the nodes popped from the stack is null, return False.

• If both nodes popped from the stack are not null, check their values.

Last, append two nodes' left- and right-nodes onto the stack for the next iteration.

🤖 Python3

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        # (base case)
        if not p and not q: return True
        if not p or  not q: return False
        if p.val != q.val: return False
        
        # ==================================================
        #  Tree + DFS                         (Iterative)  =
        # ==================================================
        # time  : O(n)
        # space : O(n) for worst case, O(log(n)) for avg case
        
        stack = [(p,q)]
        while stack:
            node1, node2 = stack.pop()
            
            if not node1 and not node2: continue
            
            if (node1 and not node2) or (not node1 and node2): return False
            if (node1 and node2) and node1.val != node2.val: return False
            
            stack.append((node1.left,  node2.left))
            stack.append((node1.right, node2.right))
            
        return True
    
        '''
        # ==================================================
        #  Tree + DFS                         (Recursive)  =
        # ==================================================
        # time  : O(n)
        # space : O(n) for worst case, O(log(n)) for avg case
        
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
        '''

🤖 Java

class Solution {
    /**
     * @time  : O(n)
     * @space : O(n)
     */
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
        /* base case */
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val != q.val) return false;
        
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}