LeetCode: 100 Same Tree

Problem Description

Given two binary trees, 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.

Example 1

Input:     1         1
          / \       / \
         2   3     2   3
        [1,2,3],   [1,2,3]
Output: true

Example 2

Input:     1         1
          / \       / \
         2   1     1   2
        [1,2,1],   [1,1,2]
Output: false

Solution

The idea to scan the nodes of both tree and compare their values. The problem is in which order we scan the tree structure. Note inorder scan will not work to uniquely determine a tree, instead the preorder scan could do it. Thus, we simultaneously scan both tree with the preorder order and compare values of each nodes.

a C++ Code

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(!p && !q) return true;
        if(!p or !q ) return false;
        if(p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};