145. Binary Tree Postorder Traversal

  • 39.0%

https://leetcode.com/problems/binary-tree-postorder-traversal/#/description

Given a binary tree, return the postorder traversal of its nodes’ values.

1
2
3
4
5
6
7
8
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?


方法一:

递归,此方法可用于先序、中序、后续。但是面试时肯定是不够用的。

Recursive solution

时间空间复杂度 : O(n) time and O(n) space (considering the spaces of function call stack);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
helper(root, res);
return res;
}

void helper(TreeNode* root, vector<int>& res){
if(root){
helper(root->left, res);
helper(root->right, res);
res.push_back(root->val);
}
}
};
方法二:

使用栈来保存要遍历的节点,后续是先左,后右,最后根。反过来,最后结果反转。

先根节点,然后再先右,再左。

先右,左节点就需要保存一下,所以先把左节点压入栈中,然后把右节点压入栈。

取出时,先取出右节点的,进行处理。处理完毕,再处理做节点的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
stack<TreeNode*> nodeStack;
vector<int> result;
//base case
if(root==NULL)
return result;
nodeStack.push(root);
while(!nodeStack.empty())
{
TreeNode* node= nodeStack.top();
result.push_back(node->val);
nodeStack.pop();
if(node->left)
nodeStack.push(node->left);
if(node->right)
nodeStack.push(node->right);
}
reverse(result.begin(),result.end());
return result;

}
};

思路相同,另一种写法如下:

与上述代码的不同之处在于,没有反转,而是直接在vector前面插入一个value。

v.insert(v.begin(), val);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> postorderTraversal(TreeNode *root) {
vector<int> v;
if (!root) return v;

stack<TreeNode *> s;
s.push(root);

TreeNode *p = NULL;
while(!s.empty()) {
p = s.top();
s.pop();
v.insert(v.begin(), p->val);
if (p->left) s.push(p->left);
if (p->right) s.push(p->right);
}

return v;
}

我的代码实现:

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
/**
* 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<int> res;
if(!root) return res;
stack<TreeNode*> stack;
stack.push(root);
while(!stack.empty()){
TreeNode* node = stack.top();
stack.pop();
res.push_back(node->val);
if(node->left)
stack.push(node->left);
if(node->right)
stack.push(node->right);
}
reverse(res.begin(), res.end());
return res;
}
};
方法三:

Iterative solution using stack — O(n) time and O(n) space;

我的代码实现:

Dec 10th, 2017

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stack;
TreeNode* cur = root;
while(cur!=nullptr || !stack.empty()){
if(cur){
res.push_back(cur->val);
stack.push(cur);
cur = cur->right;
}else{
TreeNode* tmp = stack.top();
stack.pop();
cur = tmp->left;
}
}
// 最后不要忘记反转
reverse(res.begin(), res.end());
return res;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> postorderTraversal(TreeNode* root) {
vector<int> nodes;
stack<TreeNode*> toVisit;
TreeNode* curNode = root;
TreeNode* lastNode = NULL;
while (curNode || !toVisit.empty()) {
if (curNode) {
toVisit.push(curNode);
curNode = curNode -> left;
}
else {
TreeNode* topNode = toVisit.top();
if (topNode -> right && lastNode != topNode -> right)
curNode = topNode -> right;
else {
nodes.push_back(topNode -> val);
lastNode = topNode;
toVisit.pop();
}
}
}
return nodes;
}

我的代码实现:

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
/**
* 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<int> res;
if(!root) return res;
stack<TreeNode*> stack;
while(root || stack.size()){
if(root){
stack.push(root);
res.push_back(root->val);
root = root->right;
}else{
TreeNode* node = stack.top();
stack.pop();
root = node->left;
}
}
reverse(res.begin(), res.end());
return res;
}
};
方法四:

https://discuss.leetcode.com/topic/14473/0-ms-clear-c-solutions-iterative-recursive-morris-traversal-3-different-solutions

Morris traversal

时间空间复杂度 : O(n) time and O(1) space!!!

Morris traversal:

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
46
void reverseNodes(TreeNode* start, TreeNode* end) {
if (start == end) return;
TreeNode* x = start;
TreeNode* y = start -> right;
TreeNode* z;
while (x != end) {
z = y -> right;
y -> right = x;
x = y;
y = z;
}
}
void reverseAddNodes(TreeNode* start, TreeNode* end, vector<int>& nodes) {
reverseNodes(start, end);
TreeNode* node = end;
while (true) {
nodes.push_back(node -> val);
if (node == start) break;
node = node -> right;
}
reverseNodes(end, start);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> nodes;
TreeNode* dump = new TreeNode(0);
dump -> left = root;
TreeNode* curNode = dump;
while (curNode) {
if (curNode -> left) {
TreeNode* predecessor = curNode -> left;
while (predecessor -> right && predecessor -> right != curNode)
predecessor = predecessor -> right;
if (!(predecessor -> right)) {
predecessor -> right = curNode;
curNode = curNode -> left;
}
else {
reverseAddNodes(curNode -> left, predecessor, nodes);
predecessor -> right = NULL;
curNode = curNode -> right;
}
}
else curNode = curNode -> right;
}
return nodes;
}

我的代码实现:

按照先序遍历,先根再右再左,然后再对vector res进行reverse

访问时使用morris遍历

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
/**
* 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<int> res;
TreeNode* cur = root;
while(cur){
if(cur->right){
TreeNode* pre = cur->right;
while(pre->left && pre->left!=cur)
pre = pre->left;
if(pre->left==cur){
pre->left = NULL;
cur = cur->left;
}else{
res.push_back(cur->val);
pre->left = cur;
cur = cur->right;
}
}else{
res.push_back(cur->val);
cur = cur->left;
}
}
reverse(res.begin(), res.end());
return res;
}
};

先序、中序、后序的迭代方法总结:

https://discuss.leetcode.com/topic/30632/preorder-inorder-and-postorder-iteratively-summarization

Preorder, Inorder, and Postorder Iteratively Summarization

Here I summarize the iterative implementation for preorder, inorder, and postorder traverse.

PRE ORDER TRAVERSE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.add(p.val); // Add before going to children
p = p.left;
} else {
TreeNode node = stack.pop();
p = node.right;
}
}
return result;
}

IN ORDER TRAVERSE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
p = p.left;
} else {
TreeNode node = stack.pop();
result.add(node.val); // Add after all left children
p = node.right;
}
}
return result;
}

POST ORDER TRAVERSE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> result = new LinkedList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
TreeNode p = root;
while(!stack.isEmpty() || p != null) {
if(p != null) {
stack.push(p);
result.addFirst(p.val); // Reverse the process of preorder
p = p.right; // Reverse the process of preorder
} else {
TreeNode node = stack.pop();
p = node.left; // Reverse the process of preorder
}
}
return result;
}

0ms, 24.98%, July 14th, 2016

https://discuss.leetcode.com/topic/2919/my-accepted-code-with-explaination-does-anyone-have-a-better-idea

My Accepted code with explaination. Does anyone have a better idea?

先进行类似于先序遍历,但是先跟后右再左,结果反转。

pre-order traversal is root-left-right, and post order is left-right-root. modify the code for pre-order to make it root-right-left, and then reverse the output so that we can get left-right-root .

  1. Create an empty stack, Push root node to the stack.
  2. Do following while stack is not empty.

    2.1. pop an item from the stack and print it.

    2.2. push the left child of popped item to stack.

    2.3. push the right child of popped item to stack.

  3. reverse the ouput.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
vector<int> postorderTraversal(TreeNode *root) {
stack<TreeNode*> nodeStack;
vector<int> result;
//base case
if(root==NULL)
return result;
nodeStack.push(root);
while(!nodeStack.empty())
{
TreeNode* node= nodeStack.top();
result.push_back(node->val);
nodeStack.pop();
if(node->left)
nodeStack.push(node->left);
if(node->right)
nodeStack.push(node->right);
}
reverse(result.begin(),result.end());
return result;

}
};

4ms, 0.62%, July 14th, 2016

https://discuss.leetcode.com/topic/7427/a-very-concise-solution

A very concise solution

i have saw lots of post in this discussion, but most of them are not concise, just share mine for your reference, writing a concise code is very important

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> postorderTraversal(TreeNode *root) {
vector<int> v;
if (!root) return v;

stack<TreeNode *> s;
s.push(root);

TreeNode *p = NULL;
while(!s.empty()) {
p = s.top();
s.pop();
v.insert(v.begin(), p->val);
if (p->left) s.push(p->left);
if (p->right) s.push(p->right);
}

return v;
}

https://discuss.leetcode.com/topic/14473/0-ms-clear-c-solutions-iterative-recursive-morris-traversal-3-different-solutions

0 ms Clear C++ solutions — iterative, recursive, Morris traversal (3 different solutions!)

Hi, this is a fundamental and yet classic problem. I share my three solutions here:

  1. Iterative solution using stack — O(n) time and O(n) space;
  2. Recursive solution — O(n) time and O(n) space (considering the spaces of function call stack);
  3. Morris traversal — O(n) time and O(1) space!!!

Iterative solution using stack:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> postorderTraversal(TreeNode* root) {
vector<int> nodes;
stack<TreeNode*> toVisit;
TreeNode* curNode = root;
TreeNode* lastNode = NULL;
while (curNode || !toVisit.empty()) {
if (curNode) {
toVisit.push(curNode);
curNode = curNode -> left;
}
else {
TreeNode* topNode = toVisit.top();
if (topNode -> right && lastNode != topNode -> right)
curNode = topNode -> right;
else {
nodes.push_back(topNode -> val);
lastNode = topNode;
toVisit.pop();
}
}
}
return nodes;
}

Recursive solution:

1
2
3
4
5
6
7
8
9
10
11
void postorder(TreeNode* root, vector<int>& nodes) {
if (!root) return;
postorder(root -> left, nodes);
postorder(root -> right, nodes);
nodes.push_back(root -> val);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> nodes;
postorder(root, nodes);
return nodes;
}

Morris traversal:

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
46
void reverseNodes(TreeNode* start, TreeNode* end) {
if (start == end) return;
TreeNode* x = start;
TreeNode* y = start -> right;
TreeNode* z;
while (x != end) {
z = y -> right;
y -> right = x;
x = y;
y = z;
}
}
void reverseAddNodes(TreeNode* start, TreeNode* end, vector<int>& nodes) {
reverseNodes(start, end);
TreeNode* node = end;
while (true) {
nodes.push_back(node -> val);
if (node == start) break;
node = node -> right;
}
reverseNodes(end, start);
}
vector<int> postorderTraversal(TreeNode* root) {
vector<int> nodes;
TreeNode* dump = new TreeNode(0);
dump -> left = root;
TreeNode* curNode = dump;
while (curNode) {
if (curNode -> left) {
TreeNode* predecessor = curNode -> left;
while (predecessor -> right && predecessor -> right != curNode)
predecessor = predecessor -> right;
if (!(predecessor -> right)) {
predecessor -> right = curNode;
curNode = curNode -> left;
}
else {
reverseAddNodes(curNode -> left, predecessor, nodes);
predecessor -> right = NULL;
curNode = curNode -> right;
}
}
else curNode = curNode -> right;
}
return nodes;
}

44ms, 81.02%, July 14th, 2016

https://discuss.leetcode.com/topic/17540/share-my-two-python-iterative-solutions-post-order-and-modified-preorder-then-reverse

Share my two Python iterative solutions, post-order and modified preorder then reverse

The first is by postorder using a flag to indicate whether the node has been visited or not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
# @param {TreeNode} root
# @return {integer[]}
def postorderTraversal(self, root):
traversal, stack = [], [(root, False)]
while stack:
node, visited = stack.pop()
if node:
if visited:
# add to result if visited
traversal.append(node.val)
else:
# post-order
stack.append((node, True))
stack.append((node.right, False))
stack.append((node.left, False))

return traversal

The 2nd uses modified preorder (right subtree first). Then reverse the result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
# @param {TreeNode} root
# @return {integer[]}
def postorderTraversal(self, root):
traversal, stack = [], [root]
while stack:
node = stack.pop()
if node:
# pre-order, right first
traversal.append(node.val)
stack.append(node.left)
stack.append(node.right)

# reverse result
return traversal[::-1]

https://discuss.leetcode.com/topic/2325/accepted-just-a-reversal-of-a-modified-pre-order-traversal

Accepted – Just a reversal of a modified Pre-order traversal

This is my accepted code. I found out that pre-order traversal is root-left-right, and post order is left-right-root. I modified the code for pre-order a little to make it root-right-left, and then reverse the output. I think others would have thought of it already, but anyways here’s my code…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
# @param root, a tree node
# @return a list of integers
def postorderTraversal(self, root):
traversalInt = list()
if root!=None:
traversal = list()
traversal.append(root)

while len(traversal)>0:
probe = traversal[0]
traversalInt.append(probe.val)
traversal.remove(probe)
if (probe.left != None):
traversal.insert(0,probe.left)
if (probe.right != None):
traversal.insert(0,probe.right)
return traversalInt[::-1]

https://discuss.leetcode.com/topic/34258/iterative-method-to-do-three-kinds-of-traversal-just-like-recursive-method-only-changing-one-line-code

Iterative method to do three kinds of traversal just like recursive method only changing one line code

For three different kinds of traversal, we only need to change the order of tuples in one line as we’ve done this in the recursive solution which is very decent and classical. Just put (0, p[1]) in different position!

For post-order traversal:

1
2
3
4
5
6
7
def postorderTraversal(self, root):
res, stack = [], [(1, root)]
while stack:
p = stack.pop()
if not p[1]: continue
stack.extend([(0, p[1]), (1, p[1].right), (1, p[1].left)]) if p[0] != 0 else res.append(p[1].val)
return res

For in-order traversal:

1
2
3
4
5
6
7
def inorderTraversal(self, root):
res, stack = [], [(1, root)]
while stack:
p = stack.pop()
if not p[1]: continue
stack.extend([(1, p[1].right), (0, p[1]), (1, p[1].left)]) if p[0] != 0 else res.append(p[1].val)
return res

For pre-order traversal:

1
2
3
4
5
6
7
def preorderTraversal(self, root):
res, stack = [], [(1, root)]
while stack:
p = stack.pop()
if not p[1]: continue
stack.extend([(1, p[1].right), (1, p[1].left), (0, p[1])]) if p[0] != 0 else res.append(p[1].val)
return res

https://discuss.leetcode.com/topic/44231/preorder-inorder-and-postorder-traversal-iterative-java-solution

Preorder, Inorder and Postorder Traversal Iterative Java Solution

Postorder traversal : Binary Tree Postorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.empty()){
root = stack.pop();
list.add(0, root.val);
if(root.left != null) stack.push(root.left);
if(root.right != null) stack.push(root.right);
}
return list;
}

Preorder traversal : Binary Tree Preorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.empty()){
root = stack.pop();
list.add(root.val);
if(root.right != null) stack.push(root.right);
if(root.left != null) stack.push(root.left);
}
return list;
}

Inorder traversal : Binary Tree Inorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
while(root != null || !stack.empty()){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
list.add(root.val);
root = root.right;
}
return list;
}
谢谢你,可爱的朋友。