145. Binary Tree Postorder Traversal
难度:Hard
刷题内容
原题连接
- 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)***
内容描述内容描述��ж内容描述治���ڣ����ж内容描述治���ڣ内容描述root->val���ɡ�
/**
* 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;
}
};
