這題我今天做contest的時候突然想起來，可以遍歷一遍來做。。感覺時間復(fù)雜度跟經(jīng)典的三行做法是一樣的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代表根節(jié)點
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }

iteration 做法

如果做minimum depth，用這個方法復(fù)雜度低。

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        //本層的node數(shù)
        int curNum = 1;
        //下一層的node數(shù)
        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;
    }