1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root, ans, 0);
        return ans;
    }

    private void dfs(TreeNode node, List<Integer> ans, int level) {
        if (node == null) {
            return;
        }
        if (level == ans.size()) {
            ans.add(node.val);
        } else {
            ans.set(level, Math.max(node.val, ans.get(level)));
        }
        dfs(node.left, ans, level + 1);
        dfs(node.right, ans, level + 1);
    }
}

就是pre-order traversal, 和level order traversal的思路一样.

时间复杂度: O(n)
空间复杂度: O(n) 用来存答案的list以及递归需要用到栈桢.