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.