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;
}
};
