题目描述
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例
给定二叉树 [3,9,20,null,null,15,7]，
image.png
返回最大深度3
题目分析
- 给定一个二叉树，无论是求其最大深度，还是最小深度，都可以用广度优先遍历来解，同一套模板，只是遍历终止条件不同。
- 递归求解
BFS求解（C++）
int maxDepth(TreeNode* root) {
if (root == NULL)
return 0;
queue<TreeNode*> Q;
Q.push(root);
int depth = 0;
while(!Q.empty()){
int sz = Q.size();
for (int i=0; i<sz; i++){
TreeNode* root = Q.front();
Q.pop();
if (root->left)
Q.push(root->left);
if (root->right)
Q.push(root->right);
}
depth += 1;
}
return depth;
}
时间复杂度O(n)，空间复杂度O(n)
递归求解(python)
def maxDepth(self, root: TreeNode) -> int:
if root == None:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right))+1
时间复杂度O(n)，空间复杂度O(height) height是二叉树的高度。
