LeetCode 100 Same Tree

Problem:

Given two binary trees, write a function to check if they are equal or not.

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

Summary:

判断两棵二叉树是否完全相同。

Analysis:

1. 判断两棵树是否完全相同，则需遍历每个节点，最容易想到的写法为递归。

 1 /**
 2  * Definition for a binary tree node.
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     bool isSameTree(TreeNode* p, TreeNode* q) {
13         if (!p && !q) {
14             return true;
15         }
16         else if (!p || !q || p->val != q->val) {
17             return false;
18         }
19         
20         return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
21     }
22 };

2. 非递归写法，利用queue对两树进行层次遍历，分别比较每个节点。

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