FilesExpand file tree

 master

/

Solution145.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

43 lines (40 loc) · 1.14 KB

 master

/

Solution145.cpp

Top

File metadata and controls

• Code
• Blame

43 lines (40 loc) · 1.14 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

//

// Solution145.cpp

// Algorithm

//

// Created by Pancf on 2019/12/21.

// Copyright © 2019 Pancf. All rights reserved.

//

#include "Solution145.hpp"

#include <stack>

using std::stack;

vector<int> Solution145::postorderTraversal(TreeNode *root) {

vector<int> rv;

if (!root) {

return rv;

}

auto cur = root;

// last用来记录上次访问过出栈的结点

TreeNode *last = nullptr;

stack<TreeNode *> st;

while (cur || !st.empty()) {

if (cur) {

// 访问左子树

st.push(cur);

cur = cur->left;

} else {

auto top = st.top();

if (!top->right || last == top->right) {

// 只有栈顶结点右子树为空或者右子树已经被访问过时，才保存栈顶节点的值，然后出栈，

// 代表以该结点为根节点的左右子树都已经被访问过

rv.push_back(top->val);

last = top;

st.pop();

} else {

// 右子树不为空且未被访问时

cur = top->right;

}

}

}

return rv;

}