题目:
给定一个二叉树 root
,返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
思路一:递归法。使用前序遍历或后序遍历,前序遍历求得树的最大深度,后序遍历求得节点的高度(根节点的高度就是树的最大深度)。本题解法使用前序遍历。
代码:
public int maxDepth(TreeNode root) {
return getDepth(root);
}
public int getDepth(TreeNode node){
if(node==null)
return 0;
int leftDepth=getDepth(node.left);
int rightDepth=getDepth(node.right);
int depth=1+Math.max(leftDepth,rightDepth);
return depth;
}
思路二:迭代法。使用层序遍历。每遍历一层,depth+1 。
代码:
public int maxDepth(TreeNode root) {
if(root==null)
return 0;
Queue<TreeNode> queue=new LinkedList<>();
int depth=0;
queue.offer(root);
while(!queue.isEmpty()){
int len=queue.size();
depth++;
while(len>0){
TreeNode node=queue.peek();
if(node.left!=null) queue.offer(node.left);
if(node.right!=null) queue.offer(node.right);
queue.poll();
len--;
}
}
return depth;
}