- // test.cpp : 定义控制台应用程序的入口点。
- //
- #include "stdafx.h"
- #include <stdio.h>
- #include <vector>
- #include <set>
- #include <stack>
- using namespace std;
- // Definition for a binary tree node.
- struct TreeNode {
- int val;
- TreeNode *left;
- TreeNode *right;
- TreeNode(int x) : val(x), left(NULL), right(NULL) {}
- };
- vector<int> postorderTraversal(TreeNode* root)
- {
- set<TreeNode*> sl;
- set<TreeNode*> sr;
- stack<TreeNode*> s2;
- vector<int> v1;
- if (root == NULL)
- return v1;
- while (1)
- {
- if (root)
- {
- if ((sl.find(root) == sl.end()))
- {
- s2.push(root);
- sl.insert(root);
- root = root->left;
- }
- else if ((sr.find(root) == sr.end()))
- {
- s2.push(root);
- sr.insert(root);
- root = root->right;
- }
- else
- {
- v1.push_back(root->val);
- if (s2.empty())
- {
- break;
- }
- root = s2.top();
- s2.pop();
- }
- }
- else
- {
- root = s2.top();
- s2.pop();
- }
- }
- return v1;
- }
- int main(void)
- {
- TreeNode d(2);
- TreeNode c(4);
- c.left = &d;
- TreeNode b(3);
- TreeNode a(1);
- // a.left = &c;
- // a.right = &b;
- postorderTraversal(&a);
- printf("%d\\n");
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/0207201512980.html
来源: http://www.codesnippet.cn/detail/0207201512980.html