后续遍历二叉树

/**
 * 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时候, 也有可能两个子节点都被压栈.