题面

对比两棵二叉树是否相同,返回结果。

思路

1. 递归解决DFS

首先判断根节点,如果都空,返回true;

如果一空一不空,返回false;

如果都不空,判断两节点值是否相同,若不同,返回false,若相同,递归左子树、右子树

源码

 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 == nullptr && q == nullptr)
14             return true;
15         else if(p == nullptr || q == nullptr)
16             return false;
17         else
18         {
19             if(p->val == q->val)
20                 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
21             else
22                 return false;
23         }
24     }
25 };

2. 层序遍历解决: 队列

1. 首先判断根节点,如果都空,返回true;

2. 如果一空一不空,返回false;

3. 如果都不空,新建队列,两节点入队。如果队列不空,出队两个元素,如果都为空,继续continue(而不是像判断头节点那样返回true),如果一空一不空,返回false;

4. 如果都不空,判断该值是否相等,若不相等,返回false; 若相等,那么分别将当前节点左孩子(2个)、右孩子(2个)入队,循环。

即:这种方法是为了在过程中返回false,最后遍历完毕,返回true.

源码

 1 class Solution {
 2 public:
 3     bool isSameTree(TreeNode* p, TreeNode* q) {
 4         if(p == nullptr && q == nullptr)
 5             return true;
 6         else if(p == nullptr || q == nullptr)
 7             return false;
 8         queue<TreeNode*> tmp;
 9         tmp.push(p); tmp.push(q);
10         while(!tmp.empty())
11         {
12             TreeNode *pp, *qq;
13             pp = tmp.front(); tmp.pop();
14             qq = tmp.front(); tmp.pop();
15             if(pp == nullptr && qq == nullptr)
16                 continue;
17             else if(pp == nullptr || qq == nullptr)
18                 return false;
19             
20             if(pp->val != qq->val)
21                 return false;
22             else
23             {
24                 tmp.push(pp->left); tmp.push(qq->left);
25                 tmp.push(pp->right); tmp.push(qq->right);
26             }
27         }
28         return true;
29     }
30 };