一年百题之 515. 在每个树行中找最大值

年纪确实大了一个 广度优先遍历写了十几分钟。记录一下思路。

题目：

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

 示例1：
输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

示例2：
输入: root = [1,2,3]
输出: [1,3]

提示：

二叉树的节点个数的范围是 [0,104]

-231 <= Node.val <= 231 - 1

其实一个队列也能完成，但是个人认为2个队列虽然牺牲了空间复杂度，更容易理解。

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($val = 0, $left = null, $right = null) {
 *         $this->val = $val;
 *         $this->left = $left;
 *         $this->right = $right;
 *     }
 * }
 */
class Solution {
    private $queue1 = [];   // 当前层的队列
    private $queue2 = [];   // 下一层的队列
    private $rs = [];
    /**
     * @param TreeNode $root
     * @return Integer[]
     */
    function largestValues($root) {
        // 如果根节点不为空，则根节点放到结果中。
        if ($root != null) {
            $this->queue1[] = $root;
        } 

        $max = PHP_INT_MIN; // 当前层最大值 默认值是最小负数
        while (count($this->queue1) > 0) {
            // 从当前层获取节点。
            $curNode = array_pop($this->queue1);
            
            // 将当前节点的 左右节点扔到队列2里去
            if ($curNode->left != null) {
                $this->queue2[] = $curNode->left;
            }

            if ($curNode->right != null) {
                $this->queue2[] = $curNode->right;
            }
            // 比较当前层的最大值。
            $max = max($max, $curNode->val);
    
            // 1.将当前层的最大值塞入结果队列。
          	// 2. 重置下一行的max为最小负数。 
            // 3. 将下一层的队列 变成当前层。
            if (empty($this->queue1)) {
                $this->rs[] = $max;
                $max = PHP_INT_MIN;
                $this->queue1 = $this->queue2;
                $this->queue2 = [];
            }
        }

        return $this->rs;
        
    }
}