1 二叉树的最大深度？
二叉树如何求最大深度呢？- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
class Solution {
public:
int getDepth(TreeNode* root){
if (root==nullptr) return 0;
int left_depth = getDepth(root->left);
int right_depth = getDepth(root->right);
int depth = max(left_depth, right_depth) + 1;
return depth;
}
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
return getDepth(root);
}
};class Solution {
public:
int getDepth(TreeNode* root, int depth){
if (root==nullptr) return depth;
depth++;
int left_depth = getDepth(root->left, depth);
int right_depth = getDepth(root->right, depth);
int max_depth = max(left_depth, right_depth);
return max_depth;
}
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
return getDepth(root, 0);
}
};2 二叉树的最小深度
二叉树的最小深度需要考虑树为空的情况：- 1 左子树为空
- 2 右子树为空
- 3 左右子树都不为空
class Solution {
public:
int getDepth(TreeNode* root, int depth){
if (root==nullptr) return depth;
depth++;
int left_depth = getDepth(root->left, depth);
int right_depth = getDepth(root->right, depth);
int min_depth;
if (root->left == nullptr) min_depth = right_depth;
else if (root->right == nullptr) min_depth = left_depth;
else if (root->left && root->right) min_depth = min(left_depth, right_depth);
return min_depth;
}
int minDepth(TreeNode* root) {
if (root==nullptr) return 0;
return getDepth(root, 0);
}
};class Solution {
public:
int getDepth(TreeNode* root){
if (root==nullptr) return 0;
int left_depth = getDepth(root->left);
int right_depth = getDepth(root->right);
int depth;
if (root->left == nullptr) depth = right_depth+1;
else if (root->right == nullptr) depth = left_depth + 1;
// 根节点和左右子树都在的节点
else depth = min(left_depth, right_depth)+1;
return depth;
}
int minDepth(TreeNode* root) {
if (root==nullptr) return 0;
return getDepth(root);
}
};