/
BinaryTreePostorderTraversal.cpp
45 lines (38 loc) · 1.16 KB
/
BinaryTreePostorderTraversal.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
//
// BinaryTreePostorderTraversal .cpp
// LeetCode
//
// Created by WangJZ on 14-3-12.
// Copyright (c) 2014年 WangJZ. All rights reserved.
// http://oj.leetcode.com/problems/binary-tree-postorder-traversal/
/*
使用栈来进行后续遍历(而不是用递归的方式)
*/
#include "leetcode_tree.h"
struct TagTreeNode{
TreeNode *treeNode;
bool tag;
TagTreeNode(int x,TreeNode *t):tag(x),treeNode(t){}
};
vector<int> postorderTraversal2(TreeNode *root) {
vector<int> retVec;
if (root == NULL) {
return retVec;
}
stack<TagTreeNode *> myStack;
myStack.push(new TagTreeNode(false, root));
while (!myStack.empty()) {
TagTreeNode *cur = myStack.top();
myStack.pop();
if (cur->tag == true) {//已经是第二次出栈
retVec.push_back(cur->treeNode->val);
}else{//首次出栈
cur->tag = true;
TreeNode *curTree = cur->treeNode;
myStack.push(cur);
if (curTree->right) myStack.push(new TagTreeNode(false,curTree->right));
if (curTree->left) myStack.push(new TagTreeNode(false,curTree->left));
}
}
return retVec;
}