Repository navigation
Expand file tree
/
Copy pathBinaryTreePostorderTravesal.java
More file actions
67 lines (62 loc) · 1.92 KB
/
Copy pathBinaryTreePostorderTravesal.java
File metadata and controls
67 lines (62 loc) · 1.92 KB
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
66
67
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
//第一种方法 将后序转换为类似前序的过程，即先访问node,然后node.right,node.left,最后将结果翻转过来
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> node=new Stack<TreeNode>();
//Stack<Integer> value=new Stack<Integer>();
ArrayList<Integer> list=new ArrayList<Integer>();
if(root!=null)
node.push(root);
while(!node.empty())
{
TreeNode treenode= node.pop();
// value.push(treenode.val);
list.add(treenode.val);
if(treenode.left!=null)
node.push(treenode.left);
if(treenode.right!=null)
node.push(treenode.right);
}
/* while(!value.empty())
list.add(value.pop());
*/
Collections.reverse(list);
return list;
}
}
//第二种方法实现真正的后序非递归
public class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<TreeNode> node=new LinkedList<TreeNode>();
ArrayList<Integer> list=new ArrayList<Integer>();
TreeNode visited=new TreeNode(-1);
TreeNode treenode=root;
while(!node.isEmpty() || treenode!=null)
{
while(treenode!=null)
{
node.push(treenode);
treenode=treenode.left;
}
treenode=node.peek();
if(treenode.right==null || visited==treenode.right)
{
list.add(treenode.val);
visited=treenode;
treenode=null;
node.pop();
}
else
treenode=treenode.right;
}
return list;
}
}