二叉树的后序遍历
一.递归写法
后序遍历:先访问左子树->再访问右子树->最后访问根节点
class Solution {
public:
vector<int> res;
void dfs(TreeNode* root){
if(!root) return;
if(root->left) dfs(root->left);
if(root->right) dfs(root->right);
res.push_back(root->val);
}
vector<int> preorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
};
二.迭代写法
写法一:
算法思想:访问一个节点就把该节点入res
,并将该节点的左节点和右节点依次入栈:原因由于栈的性质,就可以先访问右节点再访问左节点
,最终翻转res
。
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
if(!root) return {};
stack<TreeNode*> st;
st.push(root);
vector<int> res;
while(st.size()){
TreeNode*p =st.top();
st.pop();
res.push_back(p->val);
if(p->left) st.push(p->left);
if(p->right) st.push(p->right);
}
reverse(res.begin(),res.end());
return res;
}
};
写法二(前中后序遍历统一写法):
算法思想:在栈中加入一个空节点NULL
,来标记下一个节点是否应该进入res
,在循环中只需要控制当前节点的进入栈的顺序。当前节点为NULL
表示下一节点访问到答案节点,且左右子树遍历完成,故将该节点入res
。若不为NULL
,则将该节点置为答案节点,即压入NULL
,然后右,左节点依次入栈。目的:先访问左右节点,最后访问答案节点。
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
if(!root) return {};
vector<int> res;
stack<TreeNode*> st;
st.push(root);
while(st.size()){
TreeNode* p=st.top();
st.pop();
if(p){
st.push(p);
st.push(NULL);
if(p->right) st.push(p->right);
if(p->left) st.push(p->left);
}else{
p=st.top();
st.pop();
res.push_back(p->val);
}
}
return res;
}
};