104.二叉树的最大深度
代码随想录链接
题目
返回给定二叉树的最大深度.
自己的想法
层序遍历一下, 返回最后一层深度.
题解
层序遍历:
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
|
class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
int depth = 0;
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
int qsize = que.size();
depth++;
for (int i = 0; i < qsize; i++) {
TreeNode *node = que.front();
que.pop();
if (node -> left) que.push(node -> left);
if (node -> right) que.push(node -> right);
}
}
return depth;
}
};
|
递归法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
return 1 + max(maxDepth(root -> left), maxDepth(root -> right));
}
};
|
111.二叉树的最小深度
代码随想录链接
题目
返回二叉树的最小深度.
自己的想法
层序遍历, 在遇到第一个无左右孩子的节点时, 返回当前深度.
题解
层序遍历:
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
|
class Solution {
public:
int minDepth(TreeNode* root) {
if (!root) return 0;
queue<TreeNode *> que;
que.push(root);
int level = 0;
while (!que.empty()) {
level++;
int qsize = que.size();
for (int i = 0; i < qsize; i++) {
TreeNode *node = que.front();
que.pop();
if (!(node -> left) && !(node -> right)) return level;
if (node -> left) que.push(node -> left);
if (node -> right) que.push(node -> right);
}
}
return level;
}
};
|
递归:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) return 0;
if ((root -> left == nullptr) && (root -> right != nullptr)) return 1 + minDepth(root -> right);
if ((root -> left != nullptr) && (root -> right == nullptr)) return 1 + minDepth(root -> left);
return 1 + min(minDepth(root -> left), minDepth(root -> right));
}
};
|
222.完全二叉树的节点个数
代码随想录链接
题目
统计给定的完全二叉树有多少个节点.
自己的想法
不管什么遍历, 个数查一下. 但时间复杂度是\(O(n)\).
应该要针对于完全二叉树的特性, 使用一些方法来降低时间复杂度.
题解
当做普通二叉树来层序遍历:
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
|
class Solution {
public:
int countNodes(TreeNode* root) {
if (!root) return 0;
int count = 0;
queue<TreeNode *> que;
que.push(root);
while (!que.empty()) {
int qsize = que.size();
for (int i = 0; i < qsize; i++) {
TreeNode *node = que.front();
que.pop();
count++;
if (node -> left) que.push(node -> left);
if (node -> right) que.push(node -> right);
}
}
return count;
}
};
|
当做普通二叉树来递归:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
int countNodes(TreeNode* root) {
if (!root) return 0;
return 1 + countNodes(root -> left) + countNodes(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
|
class Solution {
public:
int countNodes(TreeNode* root) {
if (!root) return 0;
TreeNode *left = root -> left;
TreeNode *right = root -> right;
int leftDepth = 0, rightDepth = 0;
while (left) {
left = left -> left;
leftDepth++;
}
while (right) {
right = right -> right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1;
}
return countNodes(root -> left) + countNodes(root -> right) + 1;
}
};
|
