515. Find Largest Value in Each Tree Row

题目描述

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的方法，一层一层的对整棵树进行遍历，从而可以找到每一层的最大值。基本可以总结为：

curStage: list of node;
curStageMaxNum: number;
nextStage: list of next stage node;
for each node in curStage:
  if node.val > curStageMaxNum:
    curStageMaxNum = node.val
  nextStage.push(node.left, node.right)
curStage = nextStage

这样一层层进行遍历，我们就可以找到每一层最大的元素。

当然，这并不是唯一的方法。既然BFS能找到每一层最大的元素，那么DFS可不可以呢？leetcode discuss中聪明的网友们给出了他们的答案。先初始化一个空的maxNumberList，由于是按层查找，我们只需要在每次DFS时，记录下当前的深度，并且这个深度作为maxNumberList的下标——那么只要DFS遍历到深度相同的节点时，就可以用下标访问的方式找到当前这个深度的最大值，并且判断是否要替代它。

function DFS(curNode, maxNumberList, height):
  if curNode == null: return
  if height >= maxNumberList.size: maxNumberList.push(curNode.value)
  else:
    maxNumberList[height] = max(maxNumberList[height], curNode.value)
  DFS(curNode.left, maxNumberList, height + 1)
  DFS(curNode.right, maxNumberList, height + 1)

时间复杂度分析

无论是DFS还是BFS，都是将所有的节点都遍历了一遍，因此复杂度为O(n)。

空间复杂度分析

BFS的有两个队列将所有节点遍历一次，因此为O(2n)。而DFS的只有一个maxNumberList，复杂度为O(logn)。

源码（BFS）

#define INF 2147483649

class Solution {
public:
  vector<int> largestValues(TreeNode* root) {
    if (root == NULL)
      return vector<int> ();
    queue<TreeNode*> findNext;
    vector<int> maxOfRows;
    maxOfRows.push_back(root->val);
    findNext.push(root);
    queue<TreeNode*> temp;
    long long max_ = -INF; // 注意要用long long 不然会溢出
    while (!findNext.empty()) {
      auto cur =  findNext.front();
      findNext.pop();
      if (cur->left) {
        temp.push(cur->left);
        if (cur->left->val > max_) {
          max_ = cur->left->val;
        }
      }
      if (cur->right) {
        temp.push(cur->right);
        if (cur->right->val > max_) {
          max_ = cur->right->val;
        }
      }
      if (findNext.empty()) {
        findNext = temp;
        if (max_ != -INF) { 
          maxOfRows.push_back(max_);
        }
        max_ = -INF;
        temp = queue<TreeNode* >();
      }
    }
    return maxOfRows;
  }
};