[LeetCode]145.Binary Tree Postorder Traversal
【题目】
Given a binary tree, return thepostordertraversal of its nodes' values.
For example:
Given binary tree{1,#,2,3}
,
1 \ 2 / 3
return[3,2,1]
.
【代码】
/*********************************
* 日期:2014-12-07
* 作者:SJF0115
* 题号: 145.Binary Tree Postorder Traversal
* 来源:https://oj.leetcode.com/problems/binary-tree-postorder-traversal/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <malloc.h>
#include <vector>
#include <stack>
using namespace std;
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<int> v;
stack<TreeNode *> stack;
TreeNode *p = root;
TreeNode *q;
do{
//遍历左子树
while(p != NULL){
stack.push(p);
p = p->left;
}
q = NULL;
while(!stack.empty()){
p = stack.top();
stack.pop();
// 右子树是否为空或者已访问过
if(p->right == q){
v.push_back(p->val);
//保留访问过的节点
q = p;
}
else{
//当前节点不能访问,p节点重新入栈
stack.push(p);
//处理右子树
p = p->right;
break;
}//if
}//while
}while(!stack.empty());//while
return v;
}
};
//按先序序列创建二叉树
int CreateBTree(TreeNode* &T){
char data;
//按先序次序输入二叉树中结点的值(一个字符),‘#’表示空树
cin>>data;
if(data == '#'){
T = NULL;
}
else{
T = (TreeNode*)malloc(sizeof(TreeNode));
//生成根结点
T->val = data-'0';
//构造左子树
CreateBTree(T->left);
//构造右子树
CreateBTree(T->right);
}
return 0;
}
int main() {
Solution solution;
TreeNode* root(0);
CreateBTree(root);
vector<int> v = solution.postorderTraversal(root);
for(int i = 0;i < v.size();i++){
cout<<v[i]<<endl;
}
}
【代码二】
/*------------------------------------------------
* 日期:2015-03-25
* 作者:SJF0115
* 题目: 145.Binary Tree Postorder Traversal
* 来源:https://oj.leetcode.com/problems/binary-tree-postorder-traversal/
* 结果:AC
* 来源:LeetCode
* 博客:
------------------------------------------------------*/
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
// 二叉树节点结构
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(nullptr),right(nullptr){}
};
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
vector<int> result;
if(root == nullptr){
return result;
}//if
stack<TreeNode*> s;
s.push(root);
TreeNode *node;
while(!s.empty()){
node = s.top();
s.pop();
result.insert(result.begin(),node->val);
// 左子树
if(node->left){
s.push(node->left);
}//if
// 右子树
if(node->right){
s.push(node->right);
}//if
}//while
return result;
}
};
// 1.创建二叉树
void CreateTree(TreeNode* &root){
int val;
//按先序次序输入二叉树中结点的值,‘-1’表示空树
cin>>val;
// 空节点
if(val == -1){
root = nullptr;
return;
}//if
root = new TreeNode(val);
//构造左子树
CreateTree(root->left);
//构造右子树
CreateTree(root->right);
}
int main() {
freopen("C:\\Users\\Administrator\\Desktop\\c++.txt", "r", stdin);
TreeNode* root = nullptr;
vector<int> result;
// 创建二叉树
CreateTree(root);
Solution solution;
result = solution.postorderTraversal(root);
for(int i = 0;i < result.size();++i){
cout<<result[i]<<" ";
}
cout<<endl;
return 0;
}