相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false
示例 3：
输入：p = [1,2,1], q = [1,1,2]
输出：false
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/same-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
递归终止条件：（1）如果两个二叉树都为空，则两个二叉树相同。（2）如果两个二叉树中只有一个为空，则两个二叉树一定不相同。（3）如果两个二叉树都不为空，那么首先判断它们的根节点的值是否相同，若不相同则两个二叉树一定不同，若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p==nullptr&&q==nullptr) return true;
if(p==nullptr||q==nullptr||p->val!=q->val) return false;
return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
queue<TreeNode*> qe;
qe.push(p);
qe.push(q);
while(!qe.empty()){
p = qe.front();
qe.pop();
q = qe.front();
qe.pop();
if(!p&&!q) continue;
if(!p||!q||p->val!=q->val) return false;
qe.push(p->left);
qe.push(q->left);
qe.push(p->right);
qe.push(q->right);
}
return true;
}
};
|
对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/
2 2
/ \ /
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/
2 2
\
3 3
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
与判断两个树是否相同类似，如果一个树的左子树与右子树镜像对称，那么这个树是对称的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public:
bool treeSymmetric(TreeNode *root1,TreeNode *root2){
if(root1==nullptr&&root2==nullptr) return true;
if(root1==nullptr||root2==nullptr||root1->val!=root2->val) return false;
return treeSymmetric(root1->left,root2->right)&&treeSymmetric(root1->right,root2->left);
}
bool isSymmetric(TreeNode* root) {
return treeSymmetric(root,root);
}
};
|
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
| /**迭代
*/
class Solution {
public:
bool treeSymmetric(TreeNode *root1,TreeNode *root2){
queue<TreeNode*> q;
q.push(root1);
q.push(root2);
while(!q.empty()){
root1 = q.front();
q.pop();
root2 = q.front();
q.pop();
if(!root1&&!root2) continue;
if(!root1||!root2||root1->val!=root2->val) return false;
q.push(root1->left);
q.push(root2->right);
q.push(root1->right);
q.push(root2->left);
}
return true;
}
bool isSymmetric(TreeNode* root) {
return treeSymmetric(root,root);
}
};
|
