题目

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例1：
image.png

  1. 输入: root = [1,3,2,5,3,null,9]
  2. 输出: [1,3,9]

示例2：

  1. 输入: root = [1,2,3]
  2. 输出: [1,3]

提示：

  • 二叉树的节点个数的范围是 [0,10^4]

  • -2^31 <= Node.val <= 2^(31 - 1)

    解题方法

    BFS（迭代）

    迭代遍历每层元素，记录最大值。
    时间复杂度O(n)，空间复杂度O(n)
    C++代码：

    1. /**
    2. * Definition for a binary tree node.
    3. * struct TreeNode {
    4. *     int val;
    5. *     TreeNode *left;
    6. *     TreeNode *right;
    7. *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    8. *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    9. *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    10. * };
    11. */
    12. class Solution {
    13. public:
    14.   vector<int> largestValues(TreeNode* root) {
    15.       vector<int> result;
    16.       queue<TreeNode*> nodes;
    17.       if(root != NULL)    nodes.push(root);
    18.       while(nodes.size()>0) {
    19.           int size = nodes.size();
    20.           int val = INT_MIN;
    21.           for(int i=0; i<size; i++) {
    22.               val = nodes.front()->val>val ?  nodes.front()->val : val;
    23.               if(nodes.front()->left != NULL)     nodes.push(nodes.front()->left);
    24.               if(nodes.front()->right != NULL)     nodes.push(nodes.front()->right);
    25.               nodes.pop();
    26.           }
    27.           result.push_back(val);
    28.       }
    30.       return result;
    31.   }
    32. };

    DFS（迭代）

    通过 DFS 遍历节点，更新各层最大值。
    时间复杂度O(n)，空间复杂度O(n)
    C++代码：

    /**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
  void DFS(TreeNode* cur, int level, vector<int>& vec) {
      if(cur==NULL)   return;
      if(level<vec.size()) {
          vec[level] = cur->val > vec[level] ? cur->val : vec[level];
      }
      else    vec.push_back(cur->val);
      DFS(cur->left, level+1, vec);
      DFS(cur->right, level+1, vec);
  }

  vector<int> largestValues(TreeNode* root) {
      vector<int> result;
      if(root!=NULL)    result.push_back(INT_MIN);
      int level = 0;
      DFS(root, level, result);

      return result;
  }
};