Same Tree
Post
Cancel

# LeetCode #100: Same Tree (C/C++).

easy

source: https://leetcode.com/problems/same-tree
C/C++ Solution to LeetCode problem 100. Same Tree.

## Problem

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.

## Examples

### Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

### Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

### Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

## Constraints

• The number of nodes in both trees is in the range [0, 100].
• -104 <= Node.val <= 104

## Solution

We will explore both trees simultaneously with a BFS (Breadth First Search) algorithm.

• Insert the root nodes to the queue using pair<TreeNode*, TreeNode*>.
• While the queue has nodes:
• If one node exists, but the other no, return false.
• If both nodes exist:
• If their values are different, return false.
• Insert to the queue the pointers to the left and right of each node.
• Pop the first element (pair of nodes) from the queue
• Return true.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { queue<pair<TreeNode *, TreeNode *>> bfs; bfs.push({p, q}); TreeNode *a; TreeNode *b; while (!bfs.empty()) { a = bfs.front().first; b = bfs.front().second; if ((!a && b) || (a && !b)) return false; if (a && b) { if (a->val != b->val) return false; bfs.push({a->left, b->left}); bfs.push({a->right, b->right}); } bfs.pop(); } return true; } };