LeetCode 100: Same Tree Solution

Problem Explanation

Explanation

To determine if two binary trees are the same, we need to compare their structures and values. We can perform a recursive comparison starting from the root of each tree. At each step, we check if the current nodes are equal and then recursively compare their left and right subtrees.

Algorithm:

Check if both roots are null. If so, return true.
Check if either root is null or if their values are different. If so, return false.
Recursively check if the left subtree of both trees are the same.
Recursively check if the right subtree of both trees are the same.

Time complexity: O(n) where n is the number of nodes in the tree Space complexity: O(h) where h is the height of the tree

Solution Code

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

Frequently Asked Questions

How to solve LeetCode 100 (Same Tree)?

This page provides optimized solutions for LeetCode problem 100 (Same Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 100 (Same Tree)?

The time complexity for LeetCode 100 (Same Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 100 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 100 in Java, C++, or Python.