算法每日——每日一练

💦 判断两棵二叉树是否相同

给定两个二叉树的根结点p和q，如果这两棵二叉树的结构相同，并且对应的结点具有相同的值，那么认为这两棵二叉树相同。相同则返回true，不相同则返回false。

首先看到这个题，我感觉用递归挺简单的，就想着先用迭代做一下（因为之前刚学了二叉树中序遍历的迭代方法）。因为如果不对二叉树进行遍历的话，是很难一个一个进行比较的。代码如下👇：

struct TreeNode
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //根据二叉树的中序遍历，利用栈来做，在遍历的过程进行比较
    struct TreeNode **stackp = (struct TreeNode **) malloc (sizeof(struct TreeNode *) * 100);
    struct TreeNode **stackq = (struct TreeNode **) malloc (sizeof(struct TreeNode *) * 100);
    //栈指针
    int top1 = 0,top2 = 0;
    //第一次循环这里p、q任一非空就行，后面还可以比较top来判断
    while(p || q || top1 > 0 && top2 > 0)
    {
        //先各自找到最左的那个结点
        while(p)
        {
            stackp[top1++] = p;
            p = p->left;
        }
        while(q)
        {
            stackq[top2++] = q;
            q = q->left;
        }
        //若一条路径上的结点数不相等，很明显这两棵二叉树不相等
        if(top1 != top2)
            return false;
        //出栈，向上回溯，开始遍历
        p = stackp[--top1];
        q = stackq[--top2];
        //遍历的同时进行比较
        if(p->val != q->val)
            return false;
        p = p->right;
        q = q->right;
    }
    //若循环一直顺利进行下去，那么这两棵树就是相同的
    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
40
41
42

利用递归的方式也很简单，直接判断p、q有几种情况即可，最后再递归调用函数：

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //两个都为NULL
    if(!p && !q)
        return true;
    //一个为NULL，另一个不为NULL
    else if(!p || !q)
        return false;
    //两个都不为NULL，则进行比较
    else if(p->val != q->val)
        return false;
    //两个都不为NULL，且结点值相等的情况就递归
    return (isSameTree(p->left,q->left) && isSameTree(p->right,q->right));
}
1
2
3
4
5
6
7
8
9
10
11
12
13

💦 判断是否为一棵对称二叉树

给定一棵二叉树的根结点，分别利用递归和迭代判断它是否轴对称。例如👇：

那么首先，我们就要理解清楚什么是对称的二叉树。当我第一眼看见这些例子，心里一下就能知道哪些二叉树对称，哪些不对称。但是当我写代码的时候，却迟迟没有思路。。。。

后来，我又进一步把对称二叉树的特点说出来、写出来，而不是认为自己通过视觉就能随随便便判断出来，要把它具体化，才能帮助我们理清思路。也就是我只想到它是一个对称的，但是忽略了它是怎样对称的。

作为一棵对称二叉树，可以把它左子树和右子树当作两棵独立的树来处理。对于这两棵独立的树，左子树的左孩子的值一定等于右子树的右孩子的值，左子树的右孩子的值一定等于右子树的左孩子的值。

☁️ 迭代

由中序遍历可知，我们遍历的顺序是左孩子$\to$根结点$\to$右孩子，如果我们只是这样去遍历两棵子树的话，是达不到题目的要求的。

而理想的遍历过程是，在遍历左子树的左孩子时，也在遍历右子树的右孩子；在遍历左子树的右孩子时，也在遍历右子树的左孩子，就是这么一个对称的情况。那么我们把上面说的中序遍历的顺序给它“对称”一下，也就是右孩子$\to$根结点$\to$左孩子。

对两棵子树分别用上述两种不同的中序遍历方式，即可对称地遍历一棵对称二叉树，进而在遍历的过程再去判断两个对称的结点的值是否相等。

❗️：最好是先判断是否对称，再判断值是否相等。

struct TreeNode
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};

bool isSymmetric(struct TreeNode* root)
{
    //只有一个结点的情况一定是对称的
    if(!root->left && !root->right)
        return true;
    //迭代遍历需要用利用栈的先进后出的特点
    struct TreeNode **stackp = (struct TreeNode **) malloc (sizeof(struct TreeNode *) * 500);
    struct TreeNode **stackq = (struct TreeNode **) malloc (sizeof(struct TreeNode *) * 500);
    //为了方便，设两个指针来代替左右子树
    struct TreeNode *p = root->left;
    struct TreeNode *q = root->right;
    //两个栈的指针
    int top1 = 0,top2 = 0;
    //三个条件有一个条件满足即可，就算是不对称的，在后面也会被排除掉
    while(p || q || top1 > 0 && top2 > 0)
    {
        //对p进行正常的中序遍历
        while(p)
        {
            stackp[top1++] = p;
            p = p->left;
        }
        //对q进行对称的中序遍历
        while(q)
        {
            stackq[top2++] = q;
            q = q->right;
        }
        //如果两棵子树一条路径上的结点树不相同，那么它们就一定不对称
        if(top1 != top2)
            return false;
        //出栈比较结点的值
        p = stackp[--top1];
        q = stackq[--top2];
        if(p->val != q->val)
            return false;
        p = p->right;
        q = q->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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

☁️ 递归

关于递归，这个最开始确实把我难住了。我当时是想的只调用给出的函数来实现，但给出的函数只有一个参数，我就因为这个思考了很久。。后面实在想不动了，看了一下力扣评论一个大佬写的一些思路，顿时豁然开朗，茅塞顿开，灵光一现…

因为本题只给出了一个函数，且该函数只有一个参数，而这是一个关于对称的题，用这一个函数来做可以说难度不是一点的大。所以我们可以另建一个函数，用来做递归，同时附设两个参数就好。

struct TreeNode
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
}

bool SymmeJuge(struct TreeNode *p,struct TreeNode *q)
{
    //先判断两棵子树中对称的结点是否为空
    if(p && q)
    {
        //不为空但值不相等，就不对称
        if(p->val != q->val)
            return false;
        //不为空且值相等，那么再递归
        //注意这里要同时递归left和right
        else
            return (SymmeJuge(p->left,q->right) && SymmeJuge(p->right,q->left));
    }
    //如果两个对称结点为空，则是对称的
    else if(!p && !q)
        return true;
    //这里隐含了一个为空，一个不为空的情况，且前面满足条件的二叉树已经return了
    return false;
}

bool isSymmetric(struct TreeNode* root){
    //该树只有一个结点那么一定是对称的
    if(!root->left && !root->right)
        return true;
    //如果不止一个结点，就调用SymmeJuge函数
    return (SymmeJuge(root->left,root->right));
}
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

💦 求二叉树的最大深度

给定一棵二叉树，找出其最大深度。

对于求二叉树深度这样的题，用递归来做方便理解一点。

struct TreeNode
{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};

int maxDepth(struct TreeNode* root)
{
    //判断当前结点是否为空
    if(!root)
        return 0;
    //顺着该结点的左右子树向下，返回深度大的一个
    int n = maxDepth(root->left);
    int m = maxDepth(root->right);
    if(n > m)
        return (n + 1);
    return (m + 1);   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19