望城警务督察网站建设,北京工程信息交易网,深圳购物网站建设报价,电子商务网站的后台管理系统letcode 分类练习 树的遍历 树的构建递归遍历前序遍历中序遍历后序遍历 迭代遍历前序遍历中序遍历后序遍历 层序遍历层序遍历可以解决的问题107. 二叉树的层序遍历 II199. 二叉树的右视图637. 二叉树的层平均值429. N 叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的… letcode 分类练习 树的遍历 树的构建递归遍历前序遍历中序遍历后序遍历 迭代遍历前序遍历中序遍历后序遍历 层序遍历层序遍历可以解决的问题107. 二叉树的层序遍历 II199. 二叉树的右视图637. 二叉树的层平均值429. N 叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点指针II104.二叉树的最大深度111.二叉树的最小深度 树的构建
输入数组[8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13]
#include iostream
#include vector
#include queue
#include memoryusing namespace std;// 定义二叉树节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 根据向量数组构建二叉树
TreeNode* constructBinaryTree(const vectorint* nums) {if (nums.empty() || !nums[0]) {return nullptr;}// 使用队列进行层序遍历构建树queueTreeNode* q;TreeNode* root new TreeNode(*nums[0]);q.push(root);int i 1;while (!q.empty() i nums.size()) {TreeNode* current q.front();q.pop();// 构建左子节点if (i nums.size() nums[i]) {current-left new TreeNode(*nums[i]);q.push(current-left);}i;// 构建右子节点if (i nums.size() nums[i]) {current-right new TreeNode(*nums[i]);q.push(current-right);}i;}return root;
}递归遍历
前序遍历
class Solution {
public:vectorint result;void dfs(TreeNode* root){if(!root) return;result.push_back(root-val);if(root - left)dfs(root - left);if(root - right)dfs(root- right);}vectorint preorderTraversal(TreeNode* root) {dfs(root);return result;}
};中序遍历
class Solution {
public:vectorint result;void dfs(TreeNode* root){if(!root) return;if(root-left)dfs(root-left);result.push_back(root - val);if(root-right)dfs(root-right);}vectorint inorderTraversal(TreeNode* root) {dfs(root);return result;}
};后序遍历
class Solution {
public:vectorint result;void dfs(TreeNode* root){if(!root) return;if(root-left)dfs(root-left);if(root-right)dfs(root-right);result.push_back(root - val);}vectorint postorderTraversal(TreeNode* root) {dfs(root);return result;}
};迭代遍历
前序遍历 class Solution {
public:vectorint preorderTraversal(TreeNode* root) {stackTreeNode* s;vectorint result;if(!root)return result;while(root || !s.empty()){while(root){s.push(root);// 这里while一直向左就开始收集result.push_back(root-val);root root - left;}TreeNode* node s.top();s.pop();root node - right;}return result;}
};中序遍历 class Solution {
public:vectorint inorderTraversal(TreeNode* root) {stackTreeNode* s;vectorint result;if(!root)return result;while(root || !s.empty()){while(root){s.push(root);root root - left;}TreeNode* node s.top();s.pop();// 弹栈的时候才收集result.push_back(node-val);root node - right;}return result;}
};后序遍历 后序遍历的迭代方式有区别就是弹栈后不是收集而是判断它的右孩子节点如果右孩子为空说明它是叶子节点这个时候我们收集到result里并且把这个标记成前驱节点root再置为空。如果右孩子不为空我们要像访问左孩子这样继续遍历。
class Solution {
public:vectorint postorderTraversal(TreeNode* root) {stackTreeNode* s;vectorint result;if(!root) return result;TreeNode* prev;while(root || !s.empty()){while(root){s.push(root);root root - left;}TreeNode* root s.top();s.pop();if(root - right nullptr root ! prev){result.push_back(root - val);prev root;root root - right;}else{s.push(root);root root - right;}}return result;}
};层序遍历 class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {queueTreeNode*q;vectorvectorint result;if(!root)return result;q.push(root);while(!q.empty()){int k q.size();vectorint tmp;for(int i 0;ik;i){TreeNode* node q.front();q.pop();tmp.push_back(node - val);if(node-left)q.push(node-left);if(node-right)q.push(node-right);}result.push_back(tmp);}return result;}
};层序遍历可以解决的问题
107. 二叉树的层序遍历 II class Solution {
public:vectorvectorint levelOrderBottom(TreeNode* root) {queueTreeNode*q;vectorvectorint result;if(!root)return result;q.push(root);while(!q.empty()){int k q.size();vectorint tmp;for(int i 0;ik;i){TreeNode* node q.front();q.pop();tmp.push_back(node - val);if(node-left)q.push(node-left);if(node-right)q.push(node-right);}result.push_back(tmp);}reverse(result.begin(), result.end());return result;}
};199. 二叉树的右视图 class Solution {
public:vectorint rightSideView(TreeNode* root) {queueTreeNode*q;vectorint result;if(!root)return result;q.push(root);while(!q.empty()){int k q.size();vectorint tmp;for(int i 0;ik;i){TreeNode* node q.front();q.pop();if(ik-1) result.push_back(node - val);if(node-left)q.push(node-left);if(node-right)q.push(node-right);}}return result;}
};637. 二叉树的层平均值 class Solution {
public:vectordouble averageOfLevels(TreeNode* root) {queueTreeNode*q;vectordouble result;if(!root)return result;q.push(root);while(!q.empty()){int k q.size();vectorint tmp;double sum 0;for(int i 0;ik;i){TreeNode* node q.front();sum node-val;q.pop();if(ik-1) result.push_back(sum/k);if(node-left)q.push(node-left);if(node-right)q.push(node-right);}}return result;}
};429. N 叉树的层序遍历 class Solution {
public:vectorvectorint levelOrder(Node* root) {queueNode* q;vectorvectorintresult;if(!root)return result;q.push(root);while(!q.empty()){int k q.size();vectorinttmp;for(int i 0;ik;i){Node* node q.front();q.pop();tmp.push_back(node-val);for(auto c : node-children){q.push(c);}}result.push_back(tmp);}return result;}
};515.在每个树行中找最大值 class Solution {
public:vectorint largestValues(TreeNode* root) {queueTreeNode* q;vectorint result;if(!root) return result;q.push(root);while(!q.empty()){int k q.size();int maxV INT_MIN;for(int i 0;ik;i){TreeNode* node q.front();q.pop();if(node - val maxV)maxV node - val;if(i k-1)result.push_back(maxV);if(node - left)q.push(node - left);if(node - right)q.push(node - right);}}return result;}
};116.填充每个节点的下一个右侧节点指针 class Solution {
public:Node* connect(Node* root) {queueNode* q;if(!root) return root;q.push(root);while(!q.empty()){int k q.size();Node* tmp NULL;for(int i 0;ik;i){Node* node q.front();q.pop();if(tmp ! NULL)tmp - next node;tmp node;if(node - left)q.push(node - left);if(node - right)q.push(node - right);}}return root;}
};117.填充每个节点的下一个右侧节点指针II class Solution {
public:Node* connect(Node* root) {queueNode* q;if(!root) return root;q.push(root);while(!q.empty()){int k q.size();Node* tmp NULL;for(int i 0;ik;i){Node* node q.front();q.pop();if(tmp ! NULL)tmp - next node;tmp node;if(node - left)q.push(node - left);if(node - right)q.push(node - right);}}return root;}
};104.二叉树的最大深度 class Solution {
public:int maxDepth(TreeNode* root) {queueTreeNode* q;if(!root) return 0;q.push(root);int count 0;while(!q.empty()){int k q.size();count;for(int i 0;ik;i){TreeNode* node q.front();q.pop();if(node - left)q.push(node - left);if(node - right)q.push(node - right);}}return count;}
};111.二叉树的最小深度
如果是叶子节点提前返回
class Solution {
public:int minDepth(TreeNode* root) {queueTreeNode* q;if(!root) return 0;q.push(root);int count 0;while(!q.empty()){int k q.size();count;for(int i 0;ik;i){TreeNode* node q.front();q.pop();if(!node - left !node - right)return count;if(node - left)q.push(node - left);if(node - right)q.push(node - right);}}return count;}
};
