104. 二叉树的最大深度

https://leetcode.cn/problems/maximum-depth-of-binary-tree/solutions/2774231/104-er-cha-shu-de-zui-da-shen-du-by-joke-tvk9

后序遍历

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int maxDepth(TreeNode *root) {
        if (root == NULL) return 0;
        int l = maxDepth(root->left) + 1;
        int r = maxDepth(root->right) + 1;
        return l > r ? l : r;
    }
};

先序遍历，有点回溯的感觉

层序遍历明天看，效率太低了

111. 二叉树的最小深度

想法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int minDepth(TreeNode *root) {
    //想法：通过层序遍历，找哪一层没有满，然后就返回此时的深度
    int mindepth = 1;
    queue<TreeNode *> q;
    if (root != NULL) q.push(root);
    while (!q.empty()) {
        int size = q.size();
        if (pow(2, mindepth - 1) != size)  return mindepth - 1;
        mindepth++;
        for (int i = 0; i < size; i++) {
            TreeNode *node = q.front();
            q.pop();
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
    }
    return mindepth - 1;
}

错误原因：没有好好审题目

题目：给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

是到最近的叶子节点，，因为上面代码的逻辑就无法判断了

想法二

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
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
#include <iostream>

using namespace std;

/**
 * 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) {}
 * };
 */


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(NULL), right(NULL) {}
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

int minDepth(TreeNode *root) {
    //想法：通过层序遍历，找第一个叶子节点出现的位置，返回此时的层数就好了
    int mindepth = 1;//假设根节点存在
    queue<TreeNode *> q;
    if (root != NULL) q.push(root);
    while (!q.empty()) {
        int size = q.size();

        for (int i = 0; i < size; i++) {
            TreeNode *node = q.front();
            q.pop();
            if (!node->left && !node->right) return mindepth;
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        //mindepth放这个位置最好
        mindepth++;
    }
    //走到这里说明root == NULL，q队列里面为空，while循环没有执行
    //如果真的走到这里来，说明没有叶子结点，说明树为空，此时返回0就好了
    return 0;
}
int main() {
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(3, NULL, node2);
    TreeNode *node1 = new TreeNode(1, NULL, node3);


    printf("node1 = %d\n", minDepth(node1));
    return 0;
}

卡哥想法后序遍历

本题依然是前序遍历和后序遍历都可以，前序求的是深度，后序求的是高度。那么使用后序遍历，其实求的是根节点到叶子节点的最小距离，就是求高度的过程，不过这个最小距离 也同样是最小深度。

以下讲解中遍历顺序上依然采用后序遍历（因为要比较递归返回之后的结果，本文我也给出前序遍历的写法）。

本题还有一个误区，在处理节点的过程中，最大深度很容易理解，最小深度就不那么好理解。我就是没理解最小深度，导致题目做错了

自己根据思路尝试写一遍后序遍历1.

如果是下面这种想法就错了，就和上面的想法一一样，没有理解最小深度的题意去思考，，而是另一种和最大深度很像的想法。所以代码也写得很象，但是代码是错误的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int minDepth(TreeNode *root) {
    if(root == NULL) return 0;

    int l = minDepth(root->left);
    int r = minDepth(root->right);
    return l < r ? l + 1 : r + 1;
}
int main() {
    TreeNode *node2 = new TreeNode(2);
    TreeNode *node3 = new TreeNode(3, NULL, node2);
    TreeNode *node1 = new TreeNode(1, NULL, node3);


    printf("node1 = %d\n", minDepth(node1));
    return 0;
}

自己根据思路尝试写一遍后序遍历2

这个就是对的，关键是如果一个为空，另一个不为空,,这个时候就要返回不为空的那个子树的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minDepth(TreeNode *root) {

    if (root == NULL) return 0;
    int l = minDepth(root->left);
    int r = minDepth(root->right);
    //如果是叶子节点
    if (l == 0 && r == 0) return 1;

    //如果一个为空，另一个不为空,,这个时候就要返回不为空的那个子树的值
    else if (l == 0 && r != 0)
        return r + 1;
    else if (l != 0 && r == 0)
        return l + 1;
    //如果左右都为不为空

    return l < r ? l + 1 : r + 1;
}

卡哥想法前序遍历

我也感觉写前序遍历的代码更加符合人的思考，只要往下找，找到叶子节点返沪就好了。卡哥说后序胜在代码简洁

之后再看把，时间很紧的

222. 完全二叉树的节点个数

层序遍历

个个人第一想法：

层序遍历，统计结点个数

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:
    int countNodes(TreeNode *root) {
        int count = 0;
        //层序遍历
        //个人记忆，根节点不为空压入栈，节while循环，有node来接
        queue<TreeNode *> q;
        if (root != NULL) q.push(root);
        while (!q.empty()) {
            int size = q.size();
            count += size;//同一层的节点，只用加一次size
            for (int i = 0; i < size; i++) {
                //node真正遍历了每一个节点
                TreeNode *node = q.front();
                q.pop();
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }

        return count;
    }
};

后序遍历

自己尝试用后续便利来写，感觉思路也是类似，要让左右节点分别传数量给给根节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    //假设参数是这几个,感觉不用传引用类型的count呀,试了一下，确实不用
    int postordertraverse(TreeNode *cur) {
        //边界条件
        if (cur == NULL) return 0;
        //递归公式
        //这个时候cur肯定不是空节点，可以加1
        int left = postordertraverse(cur->left);
        int right = postordertraverse(cur->right);
        return left + right + 1;
    }
    int countNodes(TreeNode *root) {
        int count = 0;
        //后序遍历
        count = postordertraverse(root);
        return count;
    }
};

更加简单的后序遍历代码（思路一样）

1
2
3
4
5
6
7
8
9
class Solution {
public:

    int countNodes(TreeNode *root) {
        if(root == NULL) return 0;
        return 1 + countNodes(root->left) + countNodes(root->right);
    }
};

利用完全二叉树的性质

用carl哥说的利用完全二叉树的性质来做

自己第一次做，顺便自己编写了测试用例

自己写的

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
class Solution {
public:
    int maxDepthleft(TreeNode *node) {
    if (node == NULL) return 0;
    int l = maxDepthleft(node->left);
    return l + 1;
}
int maxDepthright(TreeNode *node) {
    if (node == NULL) return 0;
    int r = maxDepthright(node->right);
    return r + 1;
}
//    bool isMaxBinaryTree(TreeNode *root) {
//        return maxDepthleft(root) == maxDepthright(root);
//    }
int countNodes(TreeNode *root) {
    if (root == NULL) return 0;
    int leftheight = maxDepthleft(root);
    int rightheight = maxDepthright(root);
    if (leftheight == rightheight) return (1 << leftheight) - 1;// 2 的 h 次方 - 1
    else {
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
}
};

测试用例

错误反思

第一次写这个写错了。原因是自己在复制

1
2
3
4
5
int maxDepthleft(TreeNode *node) {
    if (node == NULL) return 0;
    int l = maxDepthleft(node->left);
    return l + 1;
}

把它们改成右边的类似操作时，只把l改成了r，但是没有把node->left改成node->right。以后这一点在二叉树的题里面一定要千万注意。同理，自己下面有一次也只把lh改成rh，lnode改成rnode，差一点点忘记把lnode->left；改成rnode->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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
#include <iostream>

using namespace std;

/**
 * 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) {}
 * };
 */

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(NULL), right(NULL) {}
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

int maxDepthleft(TreeNode *node) {
    if (node == NULL) return 0;
    int l = maxDepthleft(node->left);
    return l + 1;
}
int maxDepthright(TreeNode *node) {
    if (node == NULL) return 0;
    int r = maxDepthright(node->right);
    return r + 1;
}
//    bool isMaxBinaryTree(TreeNode *root) {
//        return maxDepthleft(root) == maxDepthright(root);
//    }
int countNodes(TreeNode *root) {
    if (root == NULL) return 0;
    int leftheight = maxDepthleft(root);
    int rightheight = maxDepthright(root);
    if (leftheight == rightheight) return (1 << leftheight) - 1;
    else {
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
}
int main() {
    TreeNode *node4 = new TreeNode(4);
    TreeNode *node5 = new TreeNode(5);
    TreeNode *node6 = new TreeNode(6);
    TreeNode *node2 = new TreeNode(2, node4, node5);
    TreeNode *node3 = new TreeNode(3, node6, NULL);
    TreeNode *node1 = new TreeNode(1, node2, node3);
    printf("node6 = %d\n", countNodes(node6));
    printf("node5 = %d\n", countNodes(node5));
    printf("node4 = %d\n", countNodes(node4));
    printf("node3 = %d\n", countNodes(node3));
    printf("node2 = %d\n", countNodes(node2));
    printf("node1 = %d\n", countNodes(node1));
    return 0;
}

看过卡哥讲解视频后自己模拟卡哥思路回忆它的代码自己写出来的

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:
    int countNodes(TreeNode *root) {
    //边界条件一
    if(root == NULL) return 0;
    //边界条件二
    int lh = 0, rh = 0;
    TreeNode* lnode = root;
    while(lnode){
        lh++;
        lnode = lnode->left;
    }
    TreeNode* rnode = root;
    while(rnode){
        rh++;
        rnode = rnode->right;
    }
    if(lh == rh) return (1 << lh) - 1;
    //递归公式
    return countNodes(root->left) + countNodes(root->right) + 1;
}
};