leetcode 515. Find Largest Value in Each Tree Row

冷不防 2022-06-13 00:28 266阅读 0赞

1.题目

找出一棵二叉树，每层节点的最大值
You need to find the largest value in each row of a binary tree.

Example:
Input:

Output: [1, 3, 9]

2.分析

考察树的遍历，这里按层遍历比较直观。BFS

3.代码

class Solution {
public:
   vector<int> largestValues(TreeNode* root) {
        vector<int> maxs;
        if (root == NULL)
            return maxs;
        queue<pair<TreeNode*,int>> nodes;
        nodes.push(pair<TreeNode*,int>(root,0));
        maxs.push_back(root->val);
        while (!nodes.empty()) {
            root = nodes.front().first;
            int level = nodes.front().second;
            nodes.pop();
            if (level+1 > maxs.size())
                maxs.push_back(root->val);
            else
                maxs[level] = maxs[level] < root->val ? root->val : maxs[level];
            if (root->left) 
                nodes.push(pair<TreeNode*, int>(root->left, level + 1));
            if (root->right) 
                nodes.push(pair<TreeNode*, int>(root->right, level + 1));           
        }
        return maxs;
    }
};