递归遍历
- 题目链接：
- 144.二叉树的前序遍历
void preRecur(vector<int>& ans, TreeNode* root) {if(root) {ans.push_back(root->val);preRecur(ans, root->left);preRecur(ans, root->right);}}
- 145.二叉树的后序遍历
void sufRecur(vector<int>& ans, TreeNode* root) {if(root) {sufRecur(ans, root->left);sufRecur(ans, root->right);ans.push_back(root->val);}}
- 94.二叉树的中序遍历
void inRecur(vector<int>& ans, TreeNode* root) {if(root) {inRecur(ans, root->left);ans.push_back(root->val);inRecur(ans, root->right);}}
层序遍历
- 题目链接：
- 144.二叉树的前序遍历
void preIter(vector<int>& ans, TreeNode* root) {stack<TreeNode*> s;s.push(root);while(!s.empty()) {TreeNode* t = s.top();ans.push_back(t->val);s.pop();if(t->right)s.push(t->right);if(t->left)s.push(t->left);}}
- 145.二叉树的后序遍历
void sufIter(vector<int>& ans, TreeNode* root) {stack<TreeNode*> s;TreeNode* cur = root;TreeNode* prev = nullptr;while(cur || !s.empty()) {while(cur) {s.push(cur);cur = cur->left;}cur = s.top();s.pop();if(cur->right == nullptr || cur->right == prev) {ans.push_back(cur->val);prev = cur;cur = nullptr;} else {s.push(cur);cur = cur->right;}}}
- 94.二叉树的中序遍历
void inIter(vector<int>& ans, TreeNode* root) {stack<TreeNode*> s;TreeNode* cur = root;while(cur || !s.empty()) {while(cur) {s.push(cur);cur = cur->left;}cur = s.top();s.pop();ans.push_back(cur->val);cur = cur->right;}}
二叉树的层序遍历
- 题目链接：
102.二叉树的层序遍历
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ans;if(!root) return ans;TreeNode* cur = nullptr;deque<TreeNode*> dq;dq.push_back(root); // 双端队列while(!dq.empty()) {vector<int> t;int n = dq.size(); // 遍历一层for(int i = 0; i < n; ++i) {cur = dq.front();dq.pop_front();t.push_back(cur->val);if(cur->left)dq.push_back(cur->left);if(cur->right)dq.push_back(cur->right);}ans.push_back(t);}return ans;}
};
107.二叉树的层次遍历II
class Solution {
public:// 思路与上题一致vector<vector<int>> levelOrderBottom(TreeNode *root) {if (root == nullptr) return {};vector<vector<int>> ans;vector<TreeNode*> cur{root};while (cur.size()) {vector<TreeNode*> nxt;vector<int> vals;for (auto node : cur) {vals.push_back(node->val);if (node->left) nxt.push_back(node->left);if (node->right) nxt.push_back(node->right);}cur = move(nxt);ans.emplace_back(vals);}ranges::reverse(ans);return ans;}
};
199.二叉树的右视图
class Solution {vector<int> ans;void dfs(TreeNode* node, int depth) {if (node == nullptr) {return;}if (depth == ans.size()) { // 这个深度首次遇到ans.push_back(node->val);}dfs(node->right, depth + 1); // 先递归右子树，保证首次遇到的一定是最右边的节点dfs(node->left, depth + 1);}public:vector<int> rightSideView(TreeNode* root) {dfs(root, 0);return ans;}
};
637.二叉树的层平均值
class Solution {
public:vector<double> averageOfLevels(TreeNode* root) {vector<double> ans;if(!root) return ans;TreeNode* cur = nullptr;deque<TreeNode*> dq;dq.push_back(root);while(!dq.empty()) {int n = dq.size();double sum = 0;for(int i = 0; i < n; ++i) {cur = dq.front();dq.pop_front();sum += cur->val; if(cur->left)dq.push_back(cur->left);if(cur->right)dq.push_back(cur->right);}ans.push_back(sum / n);}return ans;}
};
429.N叉树的层序遍历
class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>> ans;if(!root) return ans;Node* cur = nullptr;deque<Node*> dq;dq.push_back(root);while(!dq.empty()) {vector<int> t;int n = dq.size();for(int i = 0; i < n; ++i) {cur = dq.front();dq.pop_front();t.push_back(cur->val);for(Node* t : cur->children) dq.push_back(t);}ans.push_back(t);}return ans;}
};
515.在每个树行中找最大值
class Solution {
public:vector<int> largestValues(TreeNode* root) {if (!root) {return {};}vector<int> res;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int len = q.size();int maxVal = INT_MIN;while (len > 0) {len--;auto t = q.front();q.pop();maxVal = max(maxVal, t->val);if (t->left) q.push(t->left);if (t->right) q.push(t->right);}res.push_back(maxVal);}return res;}
};
116.填充每个节点的下一个右侧节点指针
class Solution {
public:Node* connect(Node* root) {if(!root) return nullptr;Node* cur = nullptr;deque<Node*> dq;dq.push_back(root);while(!dq.empty()) {int n = dq.size();for(int i = 0; i < n; ++i) {cur = dq.front();dq.pop_front();if(i != n - 1)cur->next = dq.front(); // 填充nextif(cur->left) dq.push_back(cur->left);if(cur->right) dq.push_back(cur->right);}}return root;}
};
117.填充每个节点的下一个右侧节点指针II
class Solution {
public:Node* connect(Node* root) {if(!root) return nullptr;Node* cur = nullptr;deque<Node*> dq;dq.push_back(root);while(!dq.empty()) {int n = dq.size();for(int i = 0; i < n; ++i) {cur = dq.front();dq.pop_front();if(i != n - 1)cur->next = dq.front(); // 填充nextif(cur->left) dq.push_back(cur->left);if(cur->right) dq.push_back(cur->right);}}return root;}
};
104.二叉树的最大深度
class Solution {
public:int maxDepth(TreeNode* root) {if (root == nullptr) {return 0;}int l_depth = maxDepth(root->left);int r_depth = maxDepth(root->right);return max(l_depth, r_depth) + 1; // 记录高度，记录高度最大值}
};111.二叉树的最小深度
class Solution {int ans = INT_MAX; // 遍历时记录高度，遍历到叶子节点取高度最小值void dfs(TreeNode *node, int cnt) {if (node == nullptr) {return;}cnt++;if (node->left == node->right) { // node 是叶子ans = min(ans, cnt);return;}dfs(node->left, cnt);dfs(node->right, cnt);};
public:int minDepth(TreeNode *root) {dfs(root, 0);return root ? ans : 0;}
};