104.md

104. 二叉树的最大深度

递归解法

思路

• 标签：递归
• 树的最大深度等于当前节点深度 1 加左右子树最大深度：1+max(left_height,right_height)
• 时间复杂度：
• 空间复杂度：

代码

// Java
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } 
        int left_height = maxDepth(root.left);
        int right_height = maxDepth(root.right);
        return java.lang.Math.max(left_height, right_height) + 1;
    }
}

非递归解法

• 使用 栈 和 队列 均可

思路

• 标签：使用栈
• 利用 Pair

前期错误思路

• 使用栈存放

// Java, 此代码失败
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Stack<TreeNode> stack = new Stack<TreeNode>();
        int deep = 1, maxDeep = 1;
        stack.push(root);
        TreeNode node = root.left;
        while (stack.size() > 0 || node != null) {
            while (node != null) {
                stack.push(node);
                deep++;
                node = stack.peek().left;
                if (deep > maxDeep) {
                    maxDeep = deep;
                }
            }
            if (stack.peek() == root) {
                deep = 1;
            }
            if (stack.peek().right == null){
                deep--;
            }
            node = stack.pop().right;
        }
        return maxDeep;
    }
}