题目描述
输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。
题解一
使用递归的方法比较简单,首先确定递归终止的条件,第二步找返回值,最终取左右子树深度较大的一个加1即可。
class Solution {
public int maxDepth(TreeNode root) {
if (root == null)
return 0;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}
题解二
还可以使用层次遍历的方法。与把二叉树打印成多行类似,用一个变量记录当前层节点的个数,在当前层遍历结束之后将深度加1。
class Solution {
public int maxDepth(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;
if (root == null)
return depth;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode temp = queue.poll();
if (temp.left != null)
queue.offer(temp.left);
if (temp.right != null)
queue.offer(temp.right);
}
depth++;
}
return depth;
}
}
网友评论