```
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int maxDepth(TreeNode root) {
if(root == null)return 0;
Queue<TreeNode> q = new Queue<TreeNode>();
q.enQ(root);
q.last = root;
int depth = 0;
while(q.count > 0){
TreeNode p = q.deQ();
if(p.left != null)q.enQ(p.left);
if(p.right != null)q.enQ(p.right);
if(q.last == p){
// current node is the last one on that depth
depth++;
if(q.tail != null)
q.last = q.tail.val;
}
}
return depth;
}
public class Queue<T> {
QueueNode<T> head = null, tail = null;
T last = null;
int count = 0;
public void enQ(T t){
QueueNode<T> n = new QueueNode<T>(t);
if(this.count == 0){ // pay much attention to head & tail of Queue
this.tail = n;
this.head = n;
}else{
this.tail.next = n;
this.tail = n;
}
this.count++;
}
public T deQ(){
if(this.count==0)return null;
T tmp = this.head.val;
if(head == tail){
// deQ last elem, reset head & tail
head = null;
tail = null;
}else{
this.head = this.head.next;
}
this.count--;
return tmp;
}
}
public class QueueNode<T> {
T val;
QueueNode<T> next;
public QueueNode(T t){
this.val = t;
}
}
}
```