# 145. Binary Tree Postorder Traversal

## 刷题内容

• 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 **- ʱ�临�Ӷ�: O(N)*- �ռ临�Ӷ�: O(1)***

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


˼·2 **- ʱ�临�Ӷ�: O(N)*- �ռ临�Ӷ�: O(N)***

��Ŀ���ᵽ�˲��õݹ��ñ����ķ�ʽȥ内容描述�⡣��ô���Ǿ���Ҫ��ջȥ����Ԫ�أ���ʱ�����ǻ���Ҫһ������ջ内容描述Ԫ���Ƿ�Ӧ�� pop��

/**
* Definition for a binary tree node.
* 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) {
vector<TreeNode*> v;
vector<int> ans;
vector<int> count1;
if(root)
{
v.push_back(root);
count1.push_back(0);
}
while(v.size())
{
int index = v.size();
if(!count1[index - 1] && v[index -1] ->left)
{
count1[index - 1] = 1;
v.push_back(v[index - 1] ->left);
count1.push_back(0);
}
else if(count1[index - 1] != 2 && v[index - 1] ->right)
{
count1[index - 1] = 2;
v.push_back(v[index - 1] ->right);
count1.push_back(0);
}
else
{
ans.push_back(v[index - 1] ->val);
count1.pop_back();
v.pop_back();
}
}
return ans;
}
};


apachecn/AiLearning