# 题目
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明:叶子节点是指没有子节点的节点。
示例 2:
输入:root = [1,null,2]
输出:2
104. 二叉树的最大深度 - 力扣(LeetCode)
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
** 说明:** 叶子节点是指没有子节点的节点。
示例 1:
输入:root = [3,9,20,null,null,15,7]
输出:2
示例 2:
输入:root = [2,null,3,null,4,null,5,null,6]
输出:5
111. 二叉树的最小深度 - 力扣(LeetCode)
# 分析
迭代法 层序遍历来实现最合适
class Solution { | |
public: | |
int maxDepth(TreeNode* root) { | |
if (root == NULL) return 0; | |
int depth = 0; | |
queue<TreeNode*> que; | |
que.push(root); | |
while(!que.empty()) { | |
int size = que.size(); | |
depth++; // 记录深度 | |
for (int i = 0; i < size; i++) { | |
TreeNode* node = que.front(); | |
que.pop(); | |
if (node->left) que.push(node->left); | |
if (node->right) que.push(node->right); | |
} | |
} | |
return depth; | |
} | |
}; |
递归
class solution { | |
public: | |
int getdepth(TreeNode* node) { | |
if (node == NULL) return 0; | |
int leftdepth = getdepth(node->left); // 左 | |
int rightdepth = getdepth(node->right); // 右 | |
int depth = 1 + max(leftdepth, rightdepth); // 中 | |
return depth; | |
} | |
int maxDepth(TreeNode* root) { | |
return getdepth(root); | |
} | |
}; |
最小深度要注意只有当左右孩子都为空时才说明遍历最低点
class Solution { | |
public: | |
int minDepth(TreeNode* root) { | |
if (root == NULL) return 0; | |
int depth = 0; | |
queue<TreeNode*> que; | |
que.push(root); | |
while(!que.empty()) { | |
int size = que.size(); | |
depth++; // 记录最小深度 | |
for (int i = 0; i < size; i++) { | |
TreeNode* node = que.front(); | |
que.pop(); | |
if (node->left) que.push(node->left); | |
if (node->right) que.push(node->right); | |
if (!node->left && !node->right) { // 当左右孩子都为空的时候,说明是最低点的一层了,退出 | |
return depth; | |
} | |
} | |
} | |
return depth; | |
} | |
}; |
递归
class Solution { | |
public: | |
int getDepth(TreeNode* node) { | |
if (node == NULL) return 0; | |
int leftDepth = getDepth(node->left); // 左 | |
int rightDepth = getDepth(node->right); // 右 | |
// 中 | |
// 当一个左子树为空,右不为空,这时并不是最低点 | |
if (node->left == NULL && node->right != NULL) { | |
return 1 + rightDepth; | |
} | |
// 当一个右子树为空,左不为空,这时并不是最低点 | |
if (node->left != NULL && node->right == NULL) { | |
return 1 + leftDepth; | |
} | |
int result = 1 + min(leftDepth, rightDepth); | |
return result; | |
} | |
int minDepth(TreeNode* root) { | |
return getDepth(root); | |
} | |
}; |