102.二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
示例 2：输入：root = [1] 输出：[[1]]
示例 3：输入：root = [] 输出：[]
分析:
1.层序遍历用队列模拟
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
vector<vector<int>> ans;
if (root == nullptr) {
return ans;
}
q.push(root);
while (!q.empty()) {
int len = q.size();
vector<int> levelVec;
while (len > 0) {
TreeNode* node = q.front();
int val = node->val;
q.pop();
levelVec.push_back(val);
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
--len;
}
ans.push_back(levelVec);
}
return ans;
}
};
199.二叉树的右视图
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1: 输入: [1,2,3,null,5,null,4] 输出: [1,3,4]
示例 2: 输入: [1,null,3] 输出: [1,3]
示例 3: 输入: [] 输出: []
分析:
1.层序遍历
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
queue<TreeNode*> q;
if (root == nullptr) {
return ans;
}
q.push(root);
while (!q.empty()) {
int qlen = q.size();
while (qlen > 0) {
root = q.front();
q.pop();
if (root->left != nullptr) {
q.push(root->left);
}
if (root->right != nullptr) {
q.push(root->right);
}
if (qlen == 1) {
ans.push_back(root->val);
}
--qlen;
}
}
return ans;
}
};
515.在每个树行中找最大值
给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
示例1：输入: root = [1,3,2,5,3,null,9] 输出: [1,3,9]
示例2：输入: root = [1,2,3] 输出: [1,3]
分析:
1.层序遍历, 每层取最大值
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
vector<int> ans;
if (root == nullptr)
return ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int len = q.size();
int levelMax = INT_MIN;
for (int i = 0; i < len; ++i) {
TreeNode* curNode = q.front();
q.pop();
levelMax = max(levelMax, curNode->val);
if (curNode->left != nullptr) {
q.push(curNode->left);
}
if (curNode->right != nullptr) {
q.push(curNode->right);
}
}
ans.emplace_back(levelMax);
}
return ans;
}
};
转载请注明来源, from goldandrabbit.github.io
