LeetCode - Algorithms - 144. Binary Tree Preorder 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
/**
 * 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> preorderTraversal(TreeNode root) {
    	List<Integer> list = new ArrayList<Integer>();
		if (root!=null) {
			TreeNode ptr = root;
			Stack<TreeNode> stk = new Stack<TreeNode>();
			while(!stk.isEmpty() || ptr != null) {
				if (ptr!=null) {
					list.add(ptr.val);
					stk.push(ptr);
					ptr = ptr.left;
				}
				else {
					ptr = (TreeNode) stk.peek();
					ptr = ptr.right;
					stk.pop();
				}
			}			
		}    	
    	return list;        
    }
}

Submission Detail

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