文章目录
- 二叉树
- 前序遍历
- 二叉树的前序遍历
- 二叉树展开为链表 （Hot 100）
- 中序遍历
- 二叉树的中序遍历 (Hot 100)
- 验证二叉搜索树 (Hot 100)
- 二叉搜索树中第K小的元素 (Hot 100)
- 后序遍历
- 二叉树的后序遍历
- 层序遍历
- 二叉树的层序遍历 （Hot 100）
- 二叉树的最大深度
- 翻转二叉树 （Hot 100）
- 二叉树的右视图 （Hot 100）
- 二叉树的锯齿形层序遍历
二叉树
前序遍历（Pre-order Traversal）、中序遍历（In-order Traversal）、后序遍历（Post-order Traversal）和层序遍历（Level-order Traversal）是四种常见的遍历树形结构的方法。四种遍历方法的主要区别在于它们访问节点的顺序不同。
-
前序遍历 首先访问根节点，然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然遵循前序遍历的规则。
-
中序遍历 首先遍历左子树，然后访问根节点，最后遍历右子树。在遍历左、右子树时，仍然遵循中序遍历的规则。
-
后序遍历 首先遍历左子树，然后遍历右子树，最后访问根节点。在遍历左、右子树时，仍然遵循后序遍历的规则。
前序、中序和后序遍历常用于对树形结构进行深度优先搜索（DFS）。通常使用递归或栈迭代来实现。
- 层序遍历 从根节点开始，首先访问第一层节点，然后逐层向下访问。在同一层中，按照从左到右的顺序访问节点。
层序遍历常用于对树形结构进行广度优先搜索（BFS），通常使用队列迭代来实现。
前序遍历
二叉树的前序遍历
二叉树的前序遍历
递归：
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == nullptr) return; // 递归终止条件
vec.push_back(cur->val); // 中
traversal(cur->left, vec); // 左
traversal(cur->right, vec); // 右
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
迭代：
class Solution {
public:
vector<int>preorderTraversal(TreeNode* root){
stack<TreeNode*> st;
vector<int> result;
if(root == nullptr) return result;
st.push(root);
while(!st.empty()){
TreeNode* node = st.top(); // 根节点出栈
st.pop();
result.push_back(node->val);
if(node->right) st.push(node->right); // 右子树入栈，
if(node->left) st.push(node->left); // 左子树入栈
}
return result;
}
};
二叉树展开为链表 （Hot 100）
二叉树展开为链表
class Solution {
public:
void flatten(TreeNode* root) {
vector<TreeNode*> node_list;
// 前序遍历
preorderTraversal(root, node_list);
// 连接
for(int i = 1; i < node_list.size(); i++){
TreeNode* pre = node_list[i - 1], *cur = node_list[i];
pre->left = nullptr;
pre->right = cur;
}
}
void preorderTraversal(TreeNode* root, vector<TreeNode*> & node_list){
if(root == nullptr) return;
node_list.push_back(root);
preorderTraversal(root->left, node_list);
preorderTraversal(root->right, node_list);
}
};
中序遍历
二叉树的中序遍历 (Hot 100)
二叉树的中序遍历
递归
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == NULL) return;
traversal(cur->left, vec); // 左
vec.push_back(cur->val); // 中
traversal(cur->right, vec); // 右
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
迭代
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root){
vector<int> result;
stack<TreeNode*> st;
TreeNode* cur = root;
while(cur != nullptr || !st.empty()){
if(cur != nullptr){
st.push(cur);
cur = cur->left;
}else{
cur = st.top();
st.pop();
result.push_back(cur->val);
cur = cur->right;
}
}
return result;
}
};
验证二叉搜索树 (Hot 100)
验证二叉搜索树
二叉搜索树的中序遍历为递增序列
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*> stack;
long long inorder = (long long)INT_MIN - 1;
TreeNode* cur = root;
while (!stack.empty() || cur != nullptr) {
while (cur != nullptr) {
stack.push(cur);
cur = cur -> left;
}
cur = stack.top();
stack.pop();
// 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
if (cur -> val <= inorder) {
return false;
}
inorder = cur -> val;
cur = cur -> right;
}
return true;
}
};
二叉搜索树中第K小的元素 (Hot 100)
二叉搜索树中第K小的元素
class Solution {
public:
int kthSmallest(TreeNode* root, int k) {
stack<TreeNode *> stack;
TreeNode* cur = root;
while (cur != nullptr || stack.size() > 0) {
while (cur != nullptr) {
stack.push(cur);
cur = cur->left;
}
cur = stack.top();
stack.pop();
--k;
if (k == 0) {
break;
}
cur = cur->right;
}
return cur->val;
}
};
后序遍历
二叉树的后序遍历
二叉树的后序遍历
递归：
class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) {
if (cur == nullptr) return;
traversal(cur->left, vec); // 左
traversal(cur->right, vec); // 右
vec.push_back(cur->val); // 中
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
traversal(root, result);
return result;
}
};
迭代：中右左遍历，然后reverse得到左右中
class Solution {
public:
vector<int>postorderTraversal(TreeNode* root){
stack<TreeNode*> st;
vector<int> result;
if(root==NULL) return result;
st.push(root);
while(!st.empty()){
TreeNode* node = st.top();
st.pop();
result.push_back(node->val);
if(node->left) st.push(node->left);
if(node->right) st.push(node->right);
}
reverse(result.begin(), result.end());
return result;
}
};
层序遍历
二叉树的层序遍历 （Hot 100）
二叉树的层序遍历
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> que;
if(root != nullptr) que.push(root);
vector<vector<int>> result;
while(!que.empty()){
int size = que.size(); // 每一层的节点个数
vector<int> vec;
for(int i = 0; i < size; i++){
TreeNode* node = que.front();
que.pop();
vec.push_back(node->val);
if(node->left) que.push(node->left);
if(node->right) que.push(node->right);
}
result.push_back(vec);
}
return result;
}
};
二叉树的最大深度
二叉树的最大深度
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return 0;
int depth = 0;
queue<TreeNode*> que;
que.push(root);
while(!que.empty()) {
int size = que.size();
depth++; // 记录深度
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return depth;
}
};
翻转二叉树 （Hot 100）
翻转二叉树
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
swap(node->left, node->right); // 节点处理
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return root;
}
};
二叉树的右视图 （Hot 100）
二叉树的右视图
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
queue<TreeNode*> que;
if (root != NULL) que.push(root);
vector<int> result;
while (!que.empty()) {
int size = que.size();
for (int i = 0; i < size; i++) {
TreeNode* node = que.front();
que.pop();
// 将每一层的最后元素放入result数组中
if (i == (size - 1)) result.push_back(node->val);
if (node->left) que.push(node->left);
if (node->right) que.push(node->right);
}
}
return result;
}
};
二叉树的锯齿形层序遍历
二叉树的锯齿形层序遍历
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
queue<TreeNode*> que;
vector<vector<int>> res;
if (root != NULL) que.push(root);
while (!que.empty()) {
vector<int> tmp;
for(int i = que.size(); i > 0; i--) {
TreeNode* node = que.front();
que.pop();
tmp.push_back(node->val);
if (node->left != NULL) que.push(node->left);
if (node->right != NULL) que.push(node->right);
}
if (res.size() % 2 == 1) reverse(tmp.begin(),tmp.end());
res.push_back(tmp);
}
return res;
}
};
