目录
1. N 叉树的层序遍历(中等)
2. 二叉树的锯齿形层序遍历(中等)
3. 二叉树的最大宽度(中等)
4. 在每个树行中找最大值(中等)
5. 找树左下角的值(中等)
6. 二叉树的右视图(中等)
1. N 叉树的层序遍历(中等)
先让根结点root入队,队列中:①
第一层遍历:让①出队,让①的孩子③②④入队,队列中:①③②④
第二层遍历:让③②④出队,让③的孩子⑤⑥入队(②④没有孩子),队列中:③②④⑤⑥
第三层遍历:让⑤⑥出队,⑤⑥没孩子。
队列为空,层序遍历结束。
代码流程设计:先让根节点入队。然后在每一轮层序遍历中,计算当前队列中节点的个数(即本层节点的个数),记为count,依次让count个节点出队,把本层节点的值放到临时数组中,并让本层节点的孩子(即下一层节点)入队。该轮层序遍历完成后,把临时数组添加到答案中。
class Solution {
public:vector<vector<int>> levelOrder(Node* root) {if (root == nullptr)return {};vector<vector<int>> ans;queue<Node*> q;q.push(root);while (!q.empty()){int count = q.size(); // 本层节点的个数vector<int> tmp; // 记录本层节点的值for (int i = 0; i < count; i++){// 本层节点出队Node* cur = q.front();q.pop();// 把本层节点的值放入临时数组中tmp.push_back(cur->val);// 本层节点的孩子(下一层节点)入队for (auto& child : cur->children){if (child != nullptr){q.push(child);}}}ans.push_back(tmp);}return ans;}
};
2. 二叉树的锯齿形层序遍历(中等)
创建一个变量level表示层数,假设二叉树从第1层开始。level为奇数,正序遍历;level为偶数,逆序遍历。
class Solution {
public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {if (root == nullptr)return {};vector<vector<int>> ans;queue<TreeNode*> q;q.push(root);int level = 1;while (!q.empty()){int count = q.size(); // 本层节点的个数vector<int> tmp; // 记录本层节点的值for (int i = 0; i < count; i++){// 本层节点出队TreeNode* cur = q.front();q.pop();// 把本层节点的值放入临时数组中tmp.push_back(cur->val);// 本层节点的孩子(下一层节点)入队if (cur->left){q.push(cur->left);}if (cur->right){q.push(cur->right);}}// 如果本层是偶数层,将临时数组反转,再放入答案中if (level % 2 == 0){reverse(tmp.begin(), tmp.end());}ans.push_back(tmp);level++;}return ans;}
};
3. 二叉树的最大宽度(中等)
利用二叉树的顺序存储方式给二叉树的节点编号,假设根结点编号为1,编号为x的节点的两个孩子的编号分别为2x和2x+1。让节点和编号一起入队,每层宽度 = 队尾编号 - 队头编号 + 1。
代码流程设计:先让根节点入队。然后在每一轮层序遍历中,计算本层宽度并更新答案,计算当前队列中节点的个数(即本层节点的个数),记为count,依次让count个节点出队,并让本层节点的孩子(即下一层节点)入队。
如果二叉树的层数非常非常非常多时,任何一种数据类型都存不下编号。因为无符号整型溢出时会自动取模,而且题目数据保证答案将会在32位带符号整数范围内,所以用unsigned int存储编号就可以保证答案正确。
class Solution {
public:int widthOfBinaryTree(TreeNode* root) {unsigned int ans = 0;queue<pair<TreeNode*, unsigned int>> q;q.push({ root,1 });while (!q.empty()){unsigned int width = q.back().second - q.front().second + 1; // 本层宽度ans = max(ans, width);int count = q.size(); // 本层节点的个数for (int i = 0; i < count; i++){// 本层节点出队TreeNode* cur = q.front().first;unsigned int num = q.front().second; // cur的编号q.pop();// 本层节点的孩子(下一层节点)入队if (cur->left){q.push({ cur->left,2 * num });}if (cur->right){q.push({ cur->right,2 * num + 1 });}}}return ans;}
};
4. 在每个树行中找最大值(中等)
层序遍历的过程中找最大值。
class Solution {
public:vector<int> largestValues(TreeNode* root) {if (root == nullptr)return {};vector<int> ans;queue<TreeNode*> q;q.push(root);while (!q.empty()){int count = q.size(); // 本层节点的个数int tmp = INT_MIN;for (int i = 0; i < count; i++){// 本层节点出队TreeNode* cur = q.front();q.pop();// 更新tmptmp = max(tmp, cur->val);// 本层节点的孩子(下一层节点)入队if (cur->left){q.push(cur->left);}if (cur->right){q.push(cur->right);}}ans.push_back(tmp);}return ans;}
};
5. 找树左下角的值(中等)
层序遍历的过程中找最左边的值。
class Solution {
public:int findBottomLeftValue(TreeNode* root) {if (root == nullptr)return {};int ans = 0;queue<TreeNode*> q;q.push(root);while (!q.empty()){int count = q.size(); // 本层节点的个数for (int i = 0; i < count; i++){// 本层节点出队TreeNode* cur = q.front();q.pop();// 如果遍历到本层最左边的节点,更新ansif (i == 0){ans = cur->val;}// 本层节点的孩子(下一层节点)入队if (cur->left){q.push(cur->left);}if (cur->right){q.push(cur->right);}}}return ans;}
};
6. 二叉树的右视图(中等)
层序遍历的过程中找最右边的值。
class Solution {
public:vector<int> rightSideView(TreeNode* root) {if (root == nullptr)return {};vector<int> ans;queue<TreeNode*> q;q.push(root);while (!q.empty()){int count = q.size(); // 本层节点的个数for (int i = 0; i < count; i++){// 本层节点出队TreeNode* cur = q.front();q.pop();// 如果遍历到本层最右边的节点,将值添加到答案if (i == count - 1){ans.push_back(cur->val);}// 本层节点的孩子(下一层节点)入队if (cur->left){q.push(cur->left);}if (cur->right){q.push(cur->right);}}}return ans;}
};