Same Tree - Leetcode Solution

The Same Tree problem on LeetCode asks you to compare two binary trees and determine if they are identical. In other words, the two trees have the same structure and the same node values.

One way to approach this problem is to use a recursive algorithm. We can start by defining a helper function that takes two tree nodes as arguments and returns a boolean value indicating whether or not the two trees are identical.

Here's the code for the helper function:

bool isSameTree(TreeNode* p, TreeNode* q) {
    // If both nodes are null, they are equal
    if (!p && !q) {
        return true;
    }
    
    // If only one node is null, they are not equal
    if (!p || !q) {
        return false;
    }
    
    // If the node values are not equal, they are not equal
    if (p->val != q->val) {
        return false;
    }
    
    // Recursively compare the left and right subtrees
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

The helper function takes two tree nodes as arguments, which represent the roots of the two trees we want to compare. We start by checking if both nodes are null. If they are, we return true, since two null nodes are considered equal.

If only one node is null, we return false, since a null node cannot be equal to a non-null node.

If the node values are not equal, we return false as well, since the two nodes are not identical.

Finally, if all the above conditions are false, we recursively compare the left and right subtrees of the two nodes by calling the helper function on each pair of corresponding left and right child nodes. If the left and right subtrees of the two nodes are also identical, the function returns true. Otherwise, it returns false.

To solve the Same Tree problem on LeetCode, we can simply call the isSameTree function on the two given tree nodes, which represent the roots of the two trees we want to compare. If the function returns true, the two trees are identical. Otherwise, they are not.

Here's the complete code for the Same Tree problem:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // If both nodes are null, they are equal
        if (!p && !q) {
            return true;
        }
        
        // If only one node is null, they are not equal
        if (!p || !q) {
            return false;
        }
        
        // If the node values are not equal, they are not equal
        if (p->val != q->val) {
            return false;
        }
        
        // Recursively compare the left and right subtrees
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

1