Day14 | 树的遍历
前序递归遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
res := make([]int, 0)
dfs(root, &res)
return res
}
func dfs(root *TreeNode, res *[]int) {
if root == nil {
return
}
*res = append(*res, root.Val)
dfs(root.Left, res)
dfs(root.Right, res)
}
C++实现
struct TreeNode {
int val;
TreeNode * left;
TreeNode * right;
TreeNode(): val(0), left(nullptr), right(nullptr);
TreeNode(int val): val(val), left(NULL), right(NULL);
TreeNode(int val, TreeNode * left, TreeNode * right): val(val), left(left), right(right);
};
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if(root == nullptr) return {};
vector<int> res;
dfs(root, res);
return res;
}
void dfs(TreeNode * root, vector<int> &res) {
if(root == nullptr) return;
res.push_back(root->val);
dfs(root->left, res);
dfs(root->right, res);
return;
}
};
前序非递归
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func preorderTraversal(root *TreeNode) []int {
// 思路：使用一个栈保存所有的节点
if root == nil {
return nil
}
res := make([]int, 0)
st := make([]*TreeNode, 0)
st = append(st, root)
for len(st) != 0 {
// 出栈
top := st[len(st)-1]
res = append(res, top.Val)
st = st[:len(st)-1]
if top.Right != nil {
st = append(st, top.Right)
}
if top.Left != nil {
st = append(st, top.Left)
}
}
return res
}
C++实现
/**
* 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) {
if(root == nullptr) return {};
vector<int> res;
stack<TreeNode *> st;
st.push(root);
while(!st.empty()) {
TreeNode * top = st.top();
res.push_back(top->val);
st.pop();
if(top->right) st.push(top->right); // 右边先入栈，这样就后出来
if(top->left) st.push(top->left);
}
return res;
}
};
后序非递归
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func postorderTraversal(root *TreeNode) []int {
// 思路：后序 左右中，和 中右左 刚好相反
if root == nil {
return nil
}
res := make([]int, 0)
st := make([]*TreeNode, 0)
st = append(st, root)
for len(st) != 0 {
top := st[len(st)-1]
res = append(res, top.Val)
st = st[:len(st)-1]
if top.Left != nil {
st = append(st, top.Left)
}
if top.Right != nil {
st = append(st, top.Right)
}
}
for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
res[i], res[j] = res[j], res[i]
}
return res
}
/**
* 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) {
// 后序顺序为 左右中 可以通过和前序一样的方法到达 中右左，然后翻转即可变成 左右中
if(root == nullptr) return {};
vector<int> res;
stack<TreeNode *> st;
st.push(root);
while(!st.empty()) {
TreeNode * top = st.top();
st.pop();
res.push_back(top->val);
if(top->left) st.push(top->left);
if(top->right) st.push(top->right);
}
// 记得一定要翻转
reverse(res.begin(), res.end());
return res;
}
};
中序非递归遍历
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func inorderTraversal(root *TreeNode) []int {
// 思路：这一题的核心在于访问和处理的顺序不一样，所以需要借用指针来控制访问的顺序，栈用来处理元素
if root == nil {
return nil
}
st := make([]*TreeNode, 0)
res := make([]int, 0)
cur := root
// 注意结束的条件: 栈中的元素全部处理完毕，指针也到达了根节点
for len(st) != 0 || cur != nil {
// 访问顺序是 左中右
if cur != nil {
st = append(st, cur)
cur = cur.Left
} else {
// 达到根节点了，开始处理
top := st[len(st)-1]
res = append(res, top.Val)
st = st[:len(st)-1]
cur = top.Right
}
}
return res
}
/**
* 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) {
if(root == nullptr) return {};
stack<TreeNode *> st;
vector<int> res;
TreeNode * cur = root;
// 循环条件是或的关系 一方面是到达了叶子结点，另一方面是左边处理完了，这个时候栈为空但是右边还没处理
while(cur != nullptr || !st.empty()) {
if(cur != nullptr) {
// 没有到结尾
st.push(cur);
cur = cur->left; // 一直往左走（左）
}else {
cur = st.top();
st.pop();
res.push_back(cur->val); // 中间的（中）
cur = cur->right; // 右边走（右）
}
}
return res;
}
};
总结
递归三要素
- 确定递归函数的参数和返回值: 注意参数是否需要使用指针，一般来说全局变量需要用数组指针
- 确定终止条件
- 确定单层递归的逻辑
- 今天的三种遍历方式都是非常简单的，特别是递归遍历
- 对于非递归遍历来说，前序后后序使用的方法相同，使用栈来保存节点
- 中序非递归遍历稍稍有点复杂，主要是因为遍历的顺序和处理的顺序不同，所以需要一个指针来作为访问的顺序，同样使用栈保存节点。指针一直往左，当处理的时候取出栈顶，这个时候将右指针加入到栈中，下次就会接着处理
评论区