LeetCode - Algorithms - 145. Binary Tree Postorder Traversal

2007年学习数据结构曾经把北大《数据结构与算法》(张铭、赵海燕、王腾蛟)教材书上的c++实现翻译为Java语言,后序周游是最难理解的,现在拿来在LeetCode上跑跑。

Java

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
68
69
70
71
72
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();

if (root!=null) {
StackElement element = null;
TreeNode ptr = root;
Stack<StackElement> stk = new Stack<StackElement>();
while(true) {
while(ptr!=null) {
element = new StackElement();
element.setTreenode(ptr);
element.setTag(Tags.Left);;
stk.push(element);
ptr = ptr.left;
}
element = (StackElement) stk.peek();
stk.pop();
ptr = element.getTreenode();
while( element.getTag()==Tags.Right ) {
list.add(element.getTreenode().val);
if (stk.isEmpty())
return list;
else {
element = (StackElement) stk.peek();
stk.pop();
ptr = element.getTreenode();
}
}
element.setTag(Tags.Right);;
stk.push(element);
ptr = ptr.right;
}
}

return list;
}
}

enum Tags {Left,Right};

final class StackElement {
private TreeNode treenode = null;
private Tags tag;

public Tags getTag() {
return tag;
}
public void setTag(Tags tag) {
this.tag = tag;
}
public TreeNode getTreenode() {
return treenode;
}
public void setTreenode(TreeNode treenode) {
this.treenode = treenode;
}

public StackElement() {
super();
}

}

Submission Detail

  • 68 / 68 test cases passed.
  • Runtime: 4 ms
  • Your runtime beats 0.68 % of java submissions.