后续遍历二叉树
binary-tree-postorder-traversal
https://www.nowcoder.com/practice/32af374b322342b68460e6fd2641dd1b?tpId=46&tqId=29035&tPage=1&rp=1&ru=%2Fta%2Fleetcode&qru=%2Fta%2Fleetcode%2Fquestion-ranking
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
stack<TreeNode*> qu ;
vector<int> res ;
if(root == NULL) return res;
TreeNode* s1 = NULL;
qu.push(root);
while(!qu.empty()){
s1 = qu.top();
if(s1->left==NULL && s1->right==NULL)
{
res.push_back(s1->val);
qu.pop();
}else {
if(s1->right){
qu.push(s1->right);
s1->right = NULL;
}
if(s1->left) {
qu.push(s1->left);
s1->left=NULL;
}
}
}
return res;
}
常见的错误写法:
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
stack<TreeNode*> qu ;
vector<int> res ;
if(root == NULL) return res;
TreeNode* s1 = NULL;
qu.push(root);
while(!qu.empty()){
s1 = qu.top();
if(s1->left==NULL && s1->right==NULL)
{
res.push_back(s1->val);
qu.pop();
}else if(s1->right){
qu.push(s1->right);
s1->right = NULL;
}
else if(s1->left) {
qu.push(s1->left);
s1->left=NULL;
}
}
return res;
}
为什么不能按照错误的写法?
因为有可能出现s1->left 或者 s1->right != NULL 的时候出现,一次只能够将一个右节点或者左节点压入栈,导致结果错误。如果是在 if(s1->left==NULL && s1->right==NULL) 为false时候, 也有可能两个子节点都被压栈.
