地址

https://leetcode.com/problems/binary-tree-postorder-traversal/

题目

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

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

Follow up: Recursive solution is trivial, could you do it iteratively?

思路

1. 递归遍历

   做法简单好写。但题目要求使用迭代算法。

2. 用栈迭代

   用栈模拟。

3. 迭代做法

   可以google一下叫做“morris遍历”的东西，这是一种空间O(1)，时间O(n)的二叉树迭代遍历算法。morris前序中序遍历都比较好些，但morris后序遍历难写一点，需要一个反向树链的操作。

PS: 我以为题目中说的迭代算法指的是让我用morris遍历，写完了才发现迭代好像还有种用栈模拟傻逼做法。。。

代码

1. 做法一

   /**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    * };
    */
   class Solution {
   public:
       vector<int> postorderTraversal(TreeNode* root) {
           vector<int> ans;
           if(root != NULL)
               dfs(root, ans);
           return ans;
       }
       
       void dfs(TreeNode* p, vector<int> &ans)
       {
           if(p->left != NULL)
               dfs(p->left, ans);
           if(p->right != NULL)
               dfs(p->right, ans);
           ans.push_back(p->val);
       }
   };

2. 做法二

   /**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
    *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
    * };
    */
   class Solution {
   public:
       vector<int> postorderTraversal(TreeNode* root) {
           vector<int> ans;
           TreeNode *last, *cur = root;
           while(cur != NULL)
           {
               last = cur->left;
               if(last != NULL)
               {
                   while(last->right != NULL && last->right != cur)
                       last = last->right;
                   //cout<<"=="<<cur->val<<endl;
                   if(last->right == NULL)
                   {
                       last->right = cur;
                       cur = cur->left;
                       continue;
                   }
                   else
                   {
                       last->right = NULL;
                       cout<<cur->left->val<<endl;
                       print(cur->left, ans);
                   }
               }
               cur = cur->right;   
           }
           print(root, ans);
           return ans;
           
       }
       
       void print(TreeNode* cur, vector<int> &ans)
       {
           TreeNode* tail = reverse(cur);
           auto p = tail;
           //cout<<p->val<<endl;
           while(p != NULL)
               ans.push_back(p->val), p = p->right;
           reverse(tail);
       }
       TreeNode* reverse(TreeNode* cur)
       {
           TreeNode *pre = NULL, *tmp, *next;
           while(cur != NULL)
           {
               next = cur->right;
               cur->right = pre;
               pre = cur;
               cur = next;
           }
           return pre;
       }
       
   };