对树的内容有点遗忘了，做一道常见的后序遍历的题目来温习一下

题目

Given a binary tree, return the postorder traversal of its nodes' values.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

题解

这题用递归解法很简单，但做这题主要的目的就是为了复习循环实现的后序遍历

递归实现

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root == NULL) return result; // special case
        
        recurse(root, result);
        return result;
    }
    
    void recurse(TreeNode* node, vector<int> &result){
        if(node == NULL) return;
        recurse(node->left, result);
        recurse(node->right, result);
        result.push_back(node->val);
    }

循环实现

这一种实现方法其实是 “逆后序遍历” 的感觉，回头再尝试有没办法正儿八经地模拟函数递归进行正向迭代。

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root == NULL) return result; // special case
        
        interate(root, result);
        return result;
    }
    void iterate(TreeNode* root, vector<int> &result){
        stack<TreeNode*> s;
        s.push(root);
        while(!s.empty()) { 
            TreeNode* ele = s.top();
            s.pop(); 
            if(ele->left != NULL) 
                s.push(ele->left); 
            if(ele->right != NULL)
                s.push(ele->right);
            result.insert(result.begin(), ele->val); 
        }
    }