/**
* 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) {}
* };
*/
递归的三要素：
- 递归函数的参数和返回值
- 确定终止条件
- 确定单层循环的逻辑
1.二叉树的前序遍历
思路1：递归
前序遍历：根节点-左子树-右子树
- 递归函数的参数和返回值：因为要对二叉树进行遍历，所以参数里应当有当前遍历到的根节点
root。要将结果保存在vector里，还应该有答案的集合ans - 确定终止条件：如果当前节点为空，说明该节点没有子节点了，直接返回即可。
- 确定单层循环的逻辑：先将当前节点存入答案里，然后递归遍历左子树和右子树
代码1：
class Solution {
public:
void dfs(TreeNode* root,vector<int>&ans){
if(root==nullptr) return ;
ans.push_back(root->val);
dfs(root->left,ans);
dfs(root->right,ans);
}
vector<int> preorderTraversal(TreeNode* root) {
vector<int>ans;
dfs(root,ans);
return ans;
}
};
思路2：非递归
栈的特点：先进后出
递归的本质是深度优先搜索，先独立的搜索完左子树再去搜索右子树。
所以在放入栈的时候应当先加入右儿子再加入左儿子，这样左儿子先出栈，并且继续遍历左子树，最终左子树再右子树前面。
代码：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int>ans;
stack<TreeNode*>stk;
if(!root) return ans;
stk.push(root);
while(!stk.empty()){
TreeNode* now=stk.top();stk.pop();
ans.push_back(now->val);
if(now->right) stk.push(now->right);
if(now->left) stk.push(now->left);
}
return ans;
}
};
2.二叉树的中序遍历
思路1：递归
中序遍历：左子树-根节点-右子树
代码1：
class Solution {
public:
void dfs(TreeNode* root,vector<int>&ans){
if(root==nullptr) return ;
dfs(root->left,ans);
ans.push_back(root->val);
dfs(root->right,ans);
}
vector<int> inorderTraversal(TreeNode* root) {
vector<int>ans;
dfs(root,ans);
return ans;
}
};
3.二叉树的后序遍历
思路1：递归
后序遍历：左子树-右子树-根节点
代码1：
class Solution {
public:
void dfs(TreeNode* root,vector<int>&ans){
if(root==nullptr) return ;
dfs(root->left,ans);
dfs(root->right,ans);
ans.push_back(root->val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int>ans;
dfs(root,ans);
return ans;
}
};
思路2：非递归
后序遍历是左右根，反转后是根右左，所以在入栈的时候先入左儿子。（跟前序遍历对比看）
代码2：
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int>ans;
stack<TreeNode*>stk;
if(!root) return ans;
stk.push(root);
while(!stk.empty()){
TreeNode* now=stk.top();stk.pop();///根右左
if(now->left) stk.push(now->left);
if(now->right) stk.push(now->right);
ans.push_back(now->val);
}
reverse(ans.begin(),ans.end());
return ans;//左右根
}
};
