【LeetCode】对称二叉树，相同的数_二叉树如果碰到了相同的数字

二叉树的题目都有两种解法，一种递归法，一般配合着回溯，一种迭代法，配合着栈和队列

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [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

递归法思路：比较两个子树是否相同，子树的比较分为内侧和外侧，结果相于

bool isSymmetric(TreeNode* root){
if(root==NULL) return true;
return compare(root->left,root->right);
}
bool compare(TreeNode* left,TreeNode* right){
if(left==NULL&&right==NULL)return true;
else if(left==NULL&&right!=NULL) return false;
else if(left!=NULL&&right==NULL) return false;
else if(left->val!=right->val) return false;
bool outside=compare(left->left,right->right);
bool insisde=compare(left->right,right->left);
return outside&&inside;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

迭代思路：用两个栈或者队列左子树左右中，右子树右左中来比较

bool isSymmetric(TreeNode* root){

queue<TreeNode*> que;
if(root==NULL) return true;
que.push(root->left);
que.push(root->right);

while(!que.empty()){
TreeNode* left=que.front();
que.pop();
TreeNode* right=que.front();
que.pop();
if(!left&&!right) continue;
else if(!left||!right||(left->val!=right->val))
return false;
que.push(left->left);
que.push(right->right);
que.push(left->right);
que.push(right->left);
}
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

本来想用两个队列来实现，后来发现一个即可，用栈也可以写。

572. 另一个树的子树

和上一题相似

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:
给定的树 s:

     3
    / \
   4   5
  / \
 1   2
给定的树 t：

   4 
  / \
 1   2
返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。

示例 2:
给定的树 s：

     3
    / \
   4   5
  / \
 1   2
    /
   0
给定的树 t：

   4
  / \
 1   2
返回 false。
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

思路：遍历S子树，然后比较是否相同，相同就继续，不同就换一个结点

/**
 * 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 isSubtree(TreeNode* s, TreeNode* t) {//递归
        queue<TreeNode*> que;
        que.push(s);
        while(!que.empty()){
            int size=que.size();
            for(int i=0;i<size;i++){
                TreeNode* cur=que.front();
                que.pop();
                if(isSame(cur,t)) return true;
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
        } 
        return false;
    }
    bool isSame(TreeNode* s,TreeNode* t){
        if(s==NULL&&t!=NULL) return false;
        else if(s!=NULL&&t==NULL) return false;
        else if(s==NULL&&t==NULL) return true;
        else if(s->val!=t->val) return false;
        
        bool leftside=isSame(s->left,t->left);
        bool rightsize=isSame(s->right,t->right);

        return leftside&&rightsize;    }
};
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

100. 相同的树

100. 相同的树
给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true
示例 2:

输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false
示例 3:

输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

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

和对称的数相似 只需要改变比较顺序

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

        bool left=isSameTree(p->left,q->left);
        bool right=isSameTree(p->right,q->right);
        return left&&right;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13