二叉树的深度

求给定的二叉树的深度

递归方法

递归方法比较简洁，理解起来也比较方便，但是树深度较深时嵌套太多

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;
}