代码随想录第十一天|二叉树的遍历方式

. - 力扣（LeetCode）. - 力扣（LeetCode）. - 力扣（LeetCode）

思路：递归遍历

class Solution {
public:vector<int> res;void preOrder(TreeNode* root){if(root!=NULL){res.push_back(root->val);preOrder(root->left);preOrder(root->right);}}void inOrder(TreeNode* root){if(root!=NULL){res.push_back(root->val);inOrder(root->left);inOrder(root->right);}}void postOrder(TreeNode* root){if(root!=NULL){res.push_back(root->val);postOrder(root->left);preOrder(root->right);}}vector<int> preorderTraversal(TreeNode* root) {preOrder(root);return res;}
};

迭代遍历

class Solution {
public:vector<int> res;void preOrder(TreeNode* root) {if (root == nullptr) return; // 处理空节点stack<TreeNode*> s;s.push(root);while (!s.empty()) {TreeNode *now = s.top();s.pop();  // 这里应该先弹出栈顶元素// 将当前结点插入结果res.push_back(now->val);// 先将右子节点压入栈，因为后入先出原则if (now->right != nullptr) {s.push(now->right);}// 再将左子节点压入栈if (now->left != nullptr) {s.push(now->left);}}}vector<int> preorderTraversal(TreeNode* root) {preOrder(root);return res;}
};

class Solution {
public:vector<int> res;void inOrder(TreeNode* root){TreeNode *cur=root;stack<TreeNode*> s;if(root==NULL) return;while(cur!=NULL||!s.empty()){if(cur!=NULL){s.push(cur);cur=cur->left;//左}//现在栈顶为最左边元素 应该访问else{cur=s.top();res.push_back(cur->val);//中s.pop();cur=cur->right;}}}vector<int> inorderTraversal(TreeNode* root) {inOrder(root);return res;}
};

class Solution {
public:vector<int> res;void postOrder(TreeNode* root) {stack<TreeNode*> s;if (root == nullptr) return;s.push(root);while (!s.empty()) {TreeNode* now = s.top();res.push_back(now->val);s.pop();// 先将左子节点压入栈，因为我们逆序遍历if (now->left != nullptr) {s.push(now->left);}// 再将右子节点压入栈if (now->right != nullptr) {s.push(now->right);}}}vector<int> postorderTraversal(TreeNode* root) {postOrder(root);// 反转结果得到正确的后序遍历reverse(res.begin(), res.end());return res;}
};

统一风格迭代法不好理解

二叉树的层序遍历

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> v;if (root == nullptr) return v;  // 根节点为空时，返回空结果queue<TreeNode*> q;q.push(root);while (!q.empty()) {int layerSize = q.size();  // 当前层的节点数量vector<int> currentLayer;  // 存储当前层的节点值for (int i = 0; i < layerSize; i++) {TreeNode* now = q.front();q.pop();currentLayer.push_back(now->val);  // 将节点值加入当前层if (now->left != nullptr) {q.push(now->left);  // 左子节点入队}if (now->right != nullptr) {q.push(now->right);  // 右子节点入队}}v.push_back(currentLayer);  // 将当前层加入结果}return v;}
};

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {queue<TreeNode*> q;vector<vector<int>> res;stack<vector<int>> r;if(root==NULL) return res;q.push(root);while(!q.empty()){int size=q.size();vector<int> now;for(int i=0;i<size;i++){TreeNode *node=q.front();q.pop();now.push_back(node->val);if(node->left!=NULL) q.push(node->left);if(node->right!=NULL) q.push(node->right);}r.push(now);}while(!r.empty()){vector<int> now=r.top();r.pop();res.push_back(now);}return res;}
};

class Solution {
public:vector<int> rightSideView(TreeNode* root) {queue<TreeNode*> q;vector<int> res;if(root==NULL) return res;q.push(root);while(!q.empty()){int size=q.size();vector<int> now;for(int i=0;i<size;i++){TreeNode *node=q.front();q.pop();if(i==size-1)res.push_back(node->val);if(node->left!=NULL) q.push(node->left);if(node->right!=NULL) q.push(node->right);}}return res;}
};

class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {queue<TreeNode*> q;vector<vector<int>> res;vector<double> r;if(root==NULL) return r;q.push(root);while(!q.empty()){int size=q.size();vector<int> now;for(int i=0;i<size;i++){TreeNode *node=q.front();q.pop();now.push_back(node->val);if(node->left!=NULL) q.push(node->left);if(node->right!=NULL) q.push(node->right);}res.push_back(now);}for(vector<int> nums:res){double sum=0;for(int num:nums){sum+=(double)num;}sum/=nums.size();r.push_back(sum);}return r;}
};

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> v;if (root == nullptr) return v;  // 根节点为空时，返回空结果queue<Node*> q;q.push(root);while (!q.empty()) {int layerSize = q.size();  // 当前层的节点数量vector<int> currentLayer;  // 存储当前层的节点值for (int i = 0; i < layerSize; i++) {Node* now = q.front();q.pop();currentLayer.push_back(now->val);  // 将节点值加入当前层for(Node *node:now->children){if(node!=NULL)q.push(node);}}v.push_back(currentLayer);  // 将当前层加入结果}return v;}
};

class Solution {
public:Node* connect(Node* root) {if (root == nullptr) return root;  // 根节点为空时，返回空结果queue<Node*> q;q.push(root);while (!q.empty()) {int layerSize = q.size();  // 当前层的节点数量Node* pre = nullptr;  // 前一个节点初始化为空for (int i = 0; i < layerSize; i++) {  // 注意循环从0开始Node* now = q.front();q.pop();if (pre != nullptr) {pre->next = now;  // 前一个节点的next指向当前节点}pre = now;  // 更新前一个节点为当前节点if (now->left != nullptr) {q.push(now->left);  // 左子节点入队}if (now->right != nullptr) {q.push(now->right);  // 右子节点入队}}// 最后一个节点的next指向nullpre->next = nullptr;}return root;}
};

class Solution {
public:int dfs(int dep,TreeNode *now){if(now==NULL){return dep;}else{int dep1 = dep, dep2 = dep;if(now->left!=NULL){dep1=dfs(dep+1,now->left);}if(now->right!=NULL){dep2=dfs(dep+1,now->right);}return max(dep1,dep2);}}int maxDepth(TreeNode* root) {if(root==NULL)return 0;return dfs(1,root);}
};

class Solution {
public:
int dfs(int dep,TreeNode *now){if(now==NULL)return INT_MAX;// 如果当前节点是叶子节点，直接返回当前深度if (now->left == NULL && now->right == NULL) {return dep;}// 递归计算左右子树的最小深度int dep1 = dfs(dep + 1, now->left);int dep2 = dfs(dep + 1, now->right);return min(dep1, dep2);  // 返回左右子树中较小的深度}int minDepth(TreeNode* root) {if(root==NULL)return 0;return dfs(1,root);}
};