letcode 分类练习 树的遍历

树的构建

输入数组：[8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13]

#include <iostream>
#include <vector>
#include <queue>
#include <memory>using namespace std;// 定义二叉树节点结构
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};// 根据向量数组构建二叉树
TreeNode* constructBinaryTree(const vector<int*>& nums) {if (nums.empty() || !nums[0]) {return nullptr;}// 使用队列进行层序遍历构建树queue<TreeNode*> 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:vector<int> 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);}vector<int> preorderTraversal(TreeNode* root) {dfs(root);return result;}
};

中序遍历

class Solution {
public:vector<int> 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);}vector<int> inorderTraversal(TreeNode* root) {dfs(root);return result;}
};

后序遍历

class Solution {
public:vector<int> 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);}vector<int> postorderTraversal(TreeNode* root) {dfs(root);return result;}
};

迭代遍历

前序遍历

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> s;vector<int> 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:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> s;vector<int> 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:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> s;vector<int> 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:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*>q;vector<vector<int>> result;if(!root)return result;q.push(root);while(!q.empty()){int k = q.size();vector<int> tmp;for(int i =0;i<k;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:vector<vector<int>> levelOrderBottom(TreeNode* root) {queue<TreeNode*>q;vector<vector<int>> result;if(!root)return result;q.push(root);while(!q.empty()){int k = q.size();vector<int> tmp;for(int i =0;i<k;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:vector<int> rightSideView(TreeNode* root) {queue<TreeNode*>q;vector<int> result;if(!root)return result;q.push(root);while(!q.empty()){int k = q.size();vector<int> tmp;for(int i =0;i<k;i++){TreeNode* node = q.front();q.pop();if(i==k-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:vector<double> averageOfLevels(TreeNode* root) {queue<TreeNode*>q;vector<double> result;if(!root)return result;q.push(root);while(!q.empty()){int k = q.size();vector<int> tmp;double sum = 0;for(int i =0;i<k;i++){TreeNode* node = q.front();sum += node->val;q.pop();if(i==k-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:vector<vector<int>> levelOrder(Node* root) {queue<Node*> q;vector<vector<int>>result;if(!root)return result;q.push(root);while(!q.empty()){int k = q.size();vector<int>tmp;for(int i =0;i<k;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:vector<int> largestValues(TreeNode* root) {queue<TreeNode*> q;vector<int> result;if(!root) return result;q.push(root);while(!q.empty()){int k = q.size();int maxV = INT_MIN;for(int i =0;i<k;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) {queue<Node*> q;if(!root) return root;q.push(root);while(!q.empty()){int k = q.size();Node* tmp = NULL;for(int i =0;i<k;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) {queue<Node*> q;if(!root) return root;q.push(root);while(!q.empty()){int k = q.size();Node* tmp = NULL;for(int i =0;i<k;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) {queue<TreeNode*> q;if(!root) return 0;q.push(root);int count = 0;while(!q.empty()){int k = q.size();count++;for(int i =0;i<k;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) {queue<TreeNode*> q;if(!root) return 0;q.push(root);int count = 0;while(!q.empty()){int k = q.size();count++;for(int i =0;i<k;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;}
};