问题
给定一个二叉树,找出其最大深度
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数
说明: 叶子节点是指没有子节点的节点
示例:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回它的最大深度 3
解法一:递归
后序遍历,因为要通过递归函数的返回值做计算树的高度
代码的逻辑是求根节点的高度,根节点的高度即为这棵树的最大深度
class Solution {
public int maxDepth(TreeNode root) {
if(root == null){
return 0;
}else{
int leftdepth = maxDepth(root.left);
int rightdepth = maxDepth(root.right);
return Math.max(leftdepth, rightdepth) + 1;
}
}
}
时间复杂度:,其中
n
为二叉树节点的个数。每个节点在递归中只被遍历一次
空间复杂度:,其中
height
表示二叉树的高度。递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于二叉树的高度
解法二:广度优先搜索
package leetcode_104;
import javax.swing.tree.TreeNode;
import java.util.LinkedList;
import java.util.Queue;
public class solution {
public int maxDepth(TreeNode root) {
if (root == null){
return 0;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
int depth = 0;
while(!queue.isEmpty()){
int size = queue.size();
for (int i = 0; i < size; i++){
TreeNode node = queue.poll();
if (node.left != null){
queue.offer(node.left);
}
if (node.right != null){
queue.offer(node.right);
}
}
depth += 1;
}
return depth;
}
}
时间复杂度:,其中
n
为二叉树的节点个数,每个节点只会被访问一次
空间复杂度:此方法空间的消耗取决于队列存储的元素数量,其在最坏情况下会达到