0.引言
● 理论基础
● 递归遍历
● 迭代遍历
● 统一迭代
1.二叉树基础
2. 二叉树的前序遍历
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Easy (71.33%) | 1023 | - |
给你二叉树的根节点 root ，返回它节点值的 前序遍历。
示例 1：
image.png
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
image.png
输入：root = [1,2]
输出：[1,2]
示例 5：
image.png
输入：root = [1,null,2]
输出：[1,2]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
2.1.递归法
/*
* @lc app=leetcode.cn id=144 lang=cpp
*
* [144] 二叉树的前序遍历
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
std::vector<int> res;
dfs(root, res);
return res;
}
private:
void dfs(TreeNode* node, std::vector<int>& res) {
if (node == nullptr) {
return;
}
res.push_back(node->val);
dfs(node->left, res);
dfs(node->right, res);
}
};
// @lc code=end
2.2.迭代法
/*
* @lc app=leetcode.cn id=144 lang=cpp
*
* [144] 二叉树的前序遍历
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
std::stack<TreeNode*> node_stack;
std::vector<int> res;
if (root == nullptr) return res;
node_stack.push(root);
while (!node_stack.empty()) {
TreeNode* curr_node = node_stack.top();
node_stack.pop();
res.push_back(curr_node->val);
// 右子节点先入栈，等会儿后出栈
if (curr_node->right) node_stack.push(curr_node->right);
if (curr_node->left) node_stack.push(curr_node->left);
}
return res;
}
};
// @lc code=end
3. 二叉树的中序遍历
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Easy (76.23%) | 1736 | - |
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
image.png
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
- 树中节点数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
3.1.递归法
/*
* @lc app=leetcode.cn id=94 lang=cpp
*
* [94] 二叉树的中序遍历
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
std::vector<int> res;
dfs(root, res);
return res;
}
private:
void dfs(TreeNode* node, std::vector<int>& res) {
if (node == nullptr) {
return;
}
dfs(node->left, res);
res.push_back(node->val);
dfs(node->right, res);
}
};
// @lc code=end
3.2.迭代法
- 由于访问顺序和处理顺序不一致
- 1.借用指针遍历访问节点；2.使用栈性质进行处理
/*
* @lc app=leetcode.cn id=94 lang=cpp
*
* [94] 二叉树的中序遍历
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
std::vector<int> res;
std::stack<TreeNode*> node_stack;
// 借用指针进行节点访问
TreeNode* cur = root;
while (cur != nullptr || !node_stack.empty()) {
// 深入到“最左”
if (cur != nullptr) {
node_stack.push(cur);
cur = cur->left;
} else {
cur = node_stack.top();
node_stack.pop();
res.push_back(cur->val);
cur = cur->right;
}
}
return res;
}
};
// @lc code=end
4. 二叉树的后序遍历
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Easy (76.31%) | 1006 | - |
给你一棵二叉树的根节点 root ，返回其节点值的 **后序遍历 **。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
- 树中节点的数目在范围
[0, 100]内 -100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
4.1.递归法
/*
* @lc app=leetcode.cn id=145 lang=cpp
*
* [145] 二叉树的后序遍历
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
std::vector<int> res;
dfs(root, res);
return res;
}
private:
void dfs(TreeNode* node, std::vector<int>& res) {
if (node == nullptr) {
return;
}
dfs(node->left, res);
dfs(node->right, res);
res.push_back(node->val);
}
};
// @lc code=end
4.2.迭代法
/*
* @lc app=leetcode.cn id=145 lang=cpp
*
* [145] 二叉树的后序遍历
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
std::vector<int> res;
std::stack<TreeNode*> node_stack;
if (root == nullptr) return res;
node_stack.push(root);
while (!node_stack.empty()) {
TreeNode* cur = node_stack.top();
node_stack.pop();
res.push_back(cur->val);
// 先入左
if (cur->left) node_stack.push(cur->left);
if (cur->right) node_stack.push(cur->right);
}
std::reverse(res.begin(), res.end());
return res;
}
};
// @lc code=end
5. 二叉树的层序遍历
| Category | Difficulty | Likes | Dislikes |
|---|---|---|---|
| algorithms | Medium (65.44%) | 1612 | - |
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
image.png
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
5.1.递归法
/*
* @lc app=leetcode.cn id=102 lang=cpp
*
* [102] 二叉树的层序遍历
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
std::vector<std::vector<int>> res;
dfs(root, 1, res);
return res;
}
private:
void dfs(TreeNode* node, int depth, std::vector<std::vector<int>>& res) {
if (node == nullptr) {
return;
}
if (res.size() < depth) {
res.push_back(std::vector<int>());
}
res[depth - 1].push_back(node->val);
dfs(node->left, depth + 1, res); // depth隐式回溯
dfs(node->right, depth + 1, res); // depth隐式回溯
}
};
// @lc code=end
5.2.迭代法
用 queue
/*
* @lc app=leetcode.cn id=102 lang=cpp
*
* [102] 二叉树的层序遍历
*/
// @lc code=start
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
* right(right) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (root == nullptr) return {};
std::vector<std::vector<int>> res;
std::queue<TreeNode*> que;
que.push(root);
while (!que.empty()) {
std::vector<int> one_level;
// int que_size = que,size();
// for (int i = 0; i < que_size; ++i) {
// 这里的size是关键，size刚好是每层的节点数
for (int i = que.size(); i > 0; --i) {
TreeNode* cur = que.front();
que.pop();
one_level.push_back(cur->val);
if (cur->left) que.push(cur->left);
if (cur->right) que.push(cur->right);
}
res.push_back(one_level);
}
return res;
}
};
// @lc code=end
