题目：
144. Binary Tree Preorder Traversal(medium)
解题思路：
使用栈模仿递归方法。
统一前、中、后的迭代遍历方法
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
Stack<TreeNode> stack = new Stack<>();
if(root != null) stack.add(root);
while(!stack.isEmpty()){
TreeNode node = stack.peek();
if(node != null){
stack.pop(); //将该结点弹出，避免重复操作，下面再将右左中节点添加到栈中
if(node.right != null) stack.push(node.right); //添加右节点
if(node.left != null) stack.push(node.left); //添加左节点
stack.push(node); //添加中节点
stack.push(null); //中节点访问过，但还没有处理，需做一下标记
}else{
stack.pop();//标记空结点弹出
node = stack.peek();//重新取出栈中元素
stack.pop();
res.add(node.val);
}
}
return res;
}
