Day13 | Part3
约 168 个字 58 行代码 预计阅读时间 1 分钟
递归 :
| int maxDepth(TreeNode* root) {
if (!root) return 0;
int maxL = maxDepth(root->left), maxR = maxDepth(root->right);
return max(maxL, maxR) + 1;
}
|
层序遍历进行迭代 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | int maxDepth(TreeNode* root) {
int depth = 0;
queue<TreeNode*> q;
if(!root) return 0;
q.push(root);
while(!q.empty()) {
int size = q.size();
depth ++;
while( size -- ) {
TreeNode* node = q.front(); q.pop();
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
}
return depth;
}
|
| int maxDepth(Node* root) {
if(!root) return 0;
int depth = 0;
for(auto i : root->children) depth = max(depth, maxDepth(i));
return 1 + depth;
}
|
最小深度是从根节点到最近 叶子节点 的最短路径上的节点数量
递归:
| int getDepth(TreeNode* node) {
if(!node) return 0;
int l = getDepth(node->left), r = getDepth(node->right); // 左 & 右
if(!node->left && node->right) return 1 + r;
if(node->left && !node->right) return 1 + l;
return 1 + min(l, r);
}
int minDepth(TreeNode* root) {
return getDepth(root);
}
|
迭代: 在上题基础上修改: 当左右孩子都空，即最低点的一层, 进行return
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | int minDepth(TreeNode* root) {
int depth = 0;
queue<TreeNode*> q;
if(!root) return 0;
q.push(root);
while(!q.empty()) {
int size = q.size();
depth ++;
while(size --) {
TreeNode * node = q.front(); q.pop();
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
if(!node->left && !node->right) return depth;
}
}
return depth;
}
|
直接左右递归计算左右子树的长度相加即可, 或者利用层序遍历,每次pop统计数量
| int countNodes(TreeNode* root) {
if(!root) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
|
Note
在完全二叉树中，如果递归向左遍历的深度 = 递归向右遍历的深度，则是满二叉树
