原题地址（中等）

方法1—递归

思路

没看清题意，就直接递归做了。。

代码

  1. class Solution {
  2. public:
  3.     vector<int> postorderTraversal(TreeNode* root) {
  4.        vector<int> v;
  5.        dfs(root, v);
  6.        return v; 
  7.     }
  9.     void dfs(TreeNode* root, vector<int>& v) {
  10.         if(!root)   return;
  11.         dfs(root->left, v);
  12.         dfs(root->right, v);
  13.         v.push_back(root->val);
  14.     }
  15. };

方法2—栈模拟递归

思路

没啥好说的，记住就好了，中序先序后序的非递归遍历，考研学过的。

代码

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode*> stk;
        TreeNode* pre = NULL;
        while(!stk.empty() || root) {
            while(root){
                stk.push(root);
                root = root->left;
            }
            root = stk.top();
            stk.pop();
            if(!root->right || root->right == pre) {
                ans.push_back(root->val);
                pre = root;
                root = NULL;
            }
            else{
                stk.push(root);
                root = root->right;
            }
        }
        return ans;
    }
};

方法3—Morris遍历

最牛的方法
Morris遍历二叉树（空间复杂度O(1)）