剑指offer（38）二叉树的深度

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
/*
//递归
public class Solution {
    public int TreeDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = TreeDepth(root.left);
        int right = TreeDepth(root.right);
        return (left > right) ? left + 1 : right + 1;
    }
}
*/

//非递归，层序遍历
import java.util.*;
public class Solution{
    public int TreeDepth(TreeNode root){
        if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        //count为现在已经遍历的节点个数，depth为深度，endStart为一层的结束，也就预示着下一层的开始
        //每当count计数已经到达了endStart了，说明这一层结束了（因为第一层是根节点，所以为初始化为1）
        //由于层序遍历队列的特性，栈中存的都是即将被遍历（弹出）的节点，所以每次一层结束了，count重新计数，depth+1，endStart重新被赋值为下一层的节点个数，即为栈现在的大小
        int count = 0, depth = 0, endStart = 1;
        while(queue.size() != 0){
            TreeNode head = queue.poll();
            count++;
            if(head.left != null){
                queue.offer(head.left);
            }
            if(head.right != null){
                queue.offer(head.right);
            }
            if(count == endStart){
                depth++;
                count = 0;
                endStart = queue.size();
            }
        }
        return depth;
    }
}