515. Find Largest Value in Each

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]

思路:和637. Average of Levels in Binary Tree(https://www.jianshu.com/p/814d871c5f6d)的思路基本相同.即层遍历二叉树,然后在每层中分别找最大的.

vector<int> largestValues(TreeNode* root) {
    queue<TreeNode*> q; //结点队列
    vector<int> res;  //输出
    if (!root) return res;  //若root为空,直接返回
    q.push(root);
    while(!q.empty()) {
        int size = q.size();  //记录此时刻队列大小(层大小)
        int max = q.front()->val;  //先假设最大值结点是队列头(很重要,不能一上来就假设max初始为0这种不严谨的写法)
        for (int i = 0; i < size; i++) {  //遍历该层,找最大值
            TreeNode* tmp = q.front();
            q.pop();
            if (tmp->val > max) max = tmp->val;
            if (tmp->left) q.push(tmp->left);
            if (tmp->right) q.push(tmp->right);
        }
        res.push_back(max);
    }
    return res;
}