Leetcode-binary-tree-postorder-traversal

题目描述

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

For example:
Given binary tree{1,#,2,3},

1
2
3
4
5
1
\
2
/
3

return[3,2,1].

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


这题考的是后序遍历树的结点,而且要求使用迭代的方法(因为递归法解这一题过于简单?)。记录上一个根时什么,在栈中看当前根,如果上一个根是当前根的孩子,这说明这个根的孩子遍历完了,可以把这个根放入result中,若没有,将左右孩子放入栈中,下个循环后序遍历左右孩子。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
import java.util.*;

public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
//TODO 用迭代法后序遍历
ArrayList<Integer> result = new ArrayList<Integer>();

if (root == null){
return result;
}

Stack<TreeNode> stack = new Stack<TreeNode>();

TreeNode pre = null;
stack.push(root);

while(!stack.isEmpty()){
TreeNode cul = stack.peek();

//当前结点左右孩子为空或左右孩子已经处理完了就处理该结点
if ((cur.left == null && cur.right == null) || (pre != null && (pre == cur.left || pre == cur.right))){
result.add(cur.val);
stack.pop();
pre = cur;
}else{
//右孩子先进栈,使左孩子在栈顶,因为要先遍历左孩子
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
}
return result;

}
}

public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
//TODO 用递归法后序遍历
ArrayList<Integer> result = new ArrayList<Integer>();

if (root == null){
return result;
}

result.addAll(postorderTraversal(root.left));
result.addAll(postorderTraversal(root.right));
result.add(root.val);

return result;

}
}