104. Maximum Depth of Binary Tre

这题我今天做contest的时候突然想起来，可以遍历一遍来做。。感觉时间复杂度跟经典的三行做法是一样的O(n)。。不过代码很冗长。

My code

        int max = 0;

    public int maxDepth(TreeNode root) {
        traverse(root, 1);
        return max;
    }

    private void traverse(TreeNode root, int lvl) {
        if (root == null) return;
        max = Math.max(lvl, max);
        traverse(root.left, lvl + 1);
        traverse(root.right, lvl + 1);
    }

三行做法：

public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
// + 1代表根节点
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

iteration 做法

如果做minimum depth，用这个方法复杂度低。

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        //本层的node数
        int curNum = 1;
        //下一层的node数
        int nextNum = 0;
        int level = 0;
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        linkedList.add(root);
        while (linkedList.size() != 0) {
            TreeNode node = linkedList.poll();
            curNum--;
            if (node.left != null) {
                linkedList.add(node.left);
                nextNum++;
            }

            if (node.right != null) {
                linkedList.add(node.right);
                nextNum++;
            }

            if (curNum == 0) {
                level++;
                curNum = nextNum;
                nextNum = 0;
            }
        }
        return level;
    }