leetcode 515. Find Largest Value in Each Tree Row 二叉树每一层最大值+广度优先遍历BFS

柔情只为你懂 2022-06-03 03:07 128阅读 0赞

You need to find the largest value in each row of a binary tree.

Example:  
Input:

1
         / \
        3   2
       / \   \  
      5   3   9

Output: \[1, 3, 9\]

本题题意很简单，就是做一个BFS广度优先遍历，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    
    /*
    struct TreeNode 
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution
    {
    public:
        vector<int> largestValues(TreeNode* root)
        {
            vector<int> res;
            if (root == NULL)
                return res;
    
            queue<TreeNode*> que;
            que.push(root);
            while (que.empty() == false)
            {
                int size = que.size();
                int maxNum = que.front()->val;
                for (int i = 0; i < size; i++)
                {
                    TreeNode* one = que.front();
                    maxNum = max(maxNum, one->val);
                    que.pop();
                    if (one->left != NULL)
                        que.push(one->left);
                    if (one->right != NULL)
                        que.push(one->right);
                }
                res.push_back(maxNum);
            }
            return res;
        }
    };