LeetCode 145. 二叉树的后序遍历
原题链接
困难
作者:
二十七杯酒
,
2020-12-23 14:48:36
,
所有人可见
,
阅读 374
二叉树后序遍历非递归(备忘)
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
TreeNode* pre = NULL;//标记
while(!empty(stk) || root){
while(root){//先向左孩子遍历
stk.push(root);
root = root->left;
}
//取出最左下节点
root = stk.top();
stk.pop();
if(!root->right || root->right == pre){//若右孩子为空或右孩子已遍历过
res.push_back(root->val);
pre = root;//记录被遍历的节点
root = nullptr;//将root置为空
}
else{
stk.push(root);
//pre = root;
//此处不加pre = root的话,pre在一次后序遍历过程中就严格按后序遍历的顺序
//存放节点的地址;若加上这句就按照程序访问节点的顺序。
root = root->right;
}
}
return res;
}
};