题目描述

你需要在二叉树的每一行中找到最大的值。

样例

输入: 

          1
         / \
        3   2
       / \   \  
      5   3   9 

输出: [1, 3, 9]

算法

(DFS) $O(n)$

• 普通的DFS递归算法，在每一个结点，判断当前层是否使第一次访问到；若是，则扩展当前答案数组记录当前层的最大值；若不是，则比较更新当前层的最大值。

时间复杂度

• 每个结点仅遍历一次，故时间复杂度为 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode *r, int dep, vector<int>& ans) {
        if (r == NULL)
            return;

        if (ans.size() == dep)
            ans.push_back(r -> val);

        if (r -> val > ans[dep])
            ans[dep] = r -> val;

        dfs(r -> left, dep + 1, ans);
        dfs(r -> right, dep + 1, ans);
    }
    vector<int> largestValues(TreeNode* root) {
        vector<int> ans;
        dfs(root, 0, ans);
        return ans;
    }
};