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]

解題思路

題目提到的，要找到每一層最大的數(shù)字，從每一層這幾個(gè)字，我們就不難想到，可以直接用BFS的方法，一層一層的對整棵樹進(jìn)行遍歷，從而可以找到每一層的最大值。基本可以總結(jié)為：

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

這樣一層層進(jìn)行遍歷，我們就可以找到每一層最大的元素。

當(dāng)然，這并不是唯一的方法。既然BFS能找到每一層最大的元素，那么DFS可不可以呢？leetcode discuss中聰明的網(wǎng)友們給出了他們的答案。先初始化一個(gè)空的maxNumberList，由于是按層查找，我們只需要在每次DFS時(shí)，記錄下當(dāng)前的深度，并且這個(gè)深度作為maxNumberList的下標(biāo)——那么只要DFS遍歷到深度相同的節(jié)點(diǎn)時(shí)，就可以用下標(biāo)訪問的方式找到當(dāng)前這個(gè)深度的最大值，并且判斷是否要替代它。

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)

時(shí)間復(fù)雜度分析

無論是DFS還是BFS，都是將所有的節(jié)點(diǎn)都遍歷了一遍，因此復(fù)雜度為O(n)。

空間復(fù)雜度分析

BFS的有兩個(gè)隊(duì)列將所有節(jié)點(diǎn)遍歷一次，因此為O(2n)。而DFS的只有一個(gè)maxNumberList，復(fù)雜度為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;
  }
};