JZ38-二叉树深度
二叉树的深度
https://www.nowcoder.com/practice/435fb86331474282a3499955f0a41e8b?tpId=13&tags=&title=&diffculty=0&judgeStatus=0&rp=1&tab=answerKey
class Solution {
public int TreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
return helper(root);
}
public int helper(TreeNode root) {
if (root == null) {
return 0;
}
int left = helper(root.left);
int right = helper(root.right);
return Math.max(left, right) + 1;
}
}
/**
* 关键点：判别队列中某一层节点出队完成的标准是什么？
* 在出队之前，此时队列中记录的只有某一层节点，所以队列的大小就是某一层节点的个数。
* 当此个数减到0的时候，则说明该层节点全部出队完成。
*/
class Solution2 {
public int TreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.add(root);
int deep = 0;
int size = 0; //用size控制deep增长的次数和时机(同一层的元素没有完全退出队列的时候deep不可以增加)
while (queue.size() != 0) {
size = queue.size();
while (size != 0) {
TreeNode temp = queue.poll();
// if (temp != null) { //这种写***多判断一次
// list.add(temp.val);
// queue.add(temp.left); //加入空节点会对深度判断有影响
// queue.add(temp.right);
// }
if (temp.left != null) {
queue.add(temp.left);
}
if (temp.right != null) {
queue.add(temp.right);
}
size--; //当size==0时说明同一层的元素遍历完成
}
deep++;
}
return deep;
}
} 
