LeetCode 每个树行中找最大值(层次遍历、后序遍历)
您需要在二叉树的每一行中找到最大的值。
示例:
输入:
1
/ \
3 2
/ \ \
5 3 9
输出: [1, 3, 9]
思路分析: 请先翻阅 LeetCode 二叉树的层次遍历
采用层次遍历,从上至下,按层进行访问,每次寻找当前层的最大值。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> result;
queue<TreeNode*> myQueue;//辅助队列,用于层次遍历
if (root == NULL) {
return result;
}
myQueue.push(root);
TreeNode *tempNodePtr = NULL;
while (!myQueue.empty()) {
int tempQueueSize = myQueue.size(), tempRes = INT_MIN;//此时队列的大小(即将访问的层的节点数目)
for (int i = 0; i < tempQueueSize; ++i) {//将此层的所有节点出队列
tempNodePtr = myQueue.front();//获取队头
myQueue.pop();
tempRes = max(tempRes, tempNodePtr->val);//更新此层最大值
if (tempNodePtr->left != NULL) {//放置左子树根节点
myQueue.push(tempNodePtr->left);
}
if (tempNodePtr->right != NULL) {//放置右子树根节点
myQueue.push(tempNodePtr->right);
}
}
result.push_back(tempRes);//放入结果
}
return result;
}
};
方法二:采用后序遍历,在访问的节点的时候加上层数标记。
请先翻阅 LeetCode 二叉树的后序遍历(递归、递推)
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> result;
vector<int> largestValues(TreeNode* root) {
myDFS(root, 1);//后序遍历
return result;
}
//后序遍历root子树,level是root处在层数(相对于根)
void myDFS(TreeNode* root, int level){
if (root == NULL){
return;
}
//先根
if (result.size() < level){
//这个层次第一次出现
result.push_back(root->val);
}
else{
//否则直接更新该层最大值
result[level - 1] = max(result[level - 1], root->val);
}
myDFS(root->left, level + 1);//后左子树
myDFS(root->right, level + 1);//再右子树
}
};