求给定的二叉树的深度
递归方法
递归方法比较简洁，理解起来也比较方便，但是树深度较深时嵌套太多
public int treeDepth(TreeNode root) {
return root == null ? 0 : Math.max(1 + treeDepth(root.left), 1 + treeDepth(root.right));
取左子树和右子树的深度最大值加1就是整棵树的深度，对于左子树和右子树又可以采取相同的方法来向下递归
非递归方法
这个可以类比二叉树的层次遍历，先来看下非递归方法怎么进行层次遍历
public void levelTravel(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
TreeNode temp;
while (!queue.isEmpty()) {
temp = queue.poll();
System.out.println(temp.val); // 打印当前值
// 如果左结点不为null，插入队列
if (temp.left != null) {
queue.add(temp.left);
}
// 如果右结点不为null，插入队列
if (temp.right != null) {
queue.add(temp.right);
}
}
}
在这个基础上，需要判断哪里是一层结束的标志
public int TreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
TreeNode temp;
int result = 0, cur, last;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
cur = 0;
last = queue.size(); // last保存当前队列里的数据长度，也就是每一层是元素个数
while (cur < last) {
temp = queue.poll();
cur++;
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
}
// 遍历完一层
result++;
}
return result;
}
