给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]     1    \     2    /   3 输出: [3,2,1]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

 

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     void dfs(TreeNode* root, vector
     
      & ans){13         if(root == NULL) return;14         if(root->left) dfs(root->left, ans);15         if(root->right) dfs(root->right, ans);16         ans.push_back(root->val);17     }18     vector
      
        postorderTraversal(TreeNode* root) {19         vector
       
         ans;20         dfs(root, ans);21         return ans;22     }23 };
       
      
     

 

迭代的实现：用栈的方式来实现

 

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 #include
     
      11 class Solution {12 public:13     vector
      
        postorderTraversal(TreeNode* root) {14         stack
       
         s;15         s.push(root);16         vector
        
          ans;17         if(root == NULL) return ans;18         while(!s.empty()){19             TreeNode* temp = s.top();20             if(temp->left){21                 s.push(temp->left);22                 temp->left = NULL;23             } else if(temp->right){24                 s.push(temp->right);25                 temp->right = NULL;26             } else{27                 ans.push_back(temp->val);28                 s.pop();29             }30         }31         return ans;32     }33 };