题目原型：
（先序）
Given a binary tree, return the preorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},
1
\
2
/
3
return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively
（中序）
return [1,3,2].
（后序）
return [3,2,1].
直接贴代码了：
public class PreorderTraversal
{
// 创建二叉树
public TreeNode createTreeNode(String[] bitree)
{
ArrayList
tree = new ArrayList
(); TreeNode root = null; int count = 0;// 用来计算已读树节点的个数 TreeNode node = null; TreeNode lchild, rchild; for (String str : bitree) { if (!str.equals("#")) { count++; // 如果是根节点 if (count == 1) { node = new TreeNode(Integer.parseInt(str)); tree.add(node); root = node; // 建左子树 lchild = leftchild(node, count, bitree); if (lchild != null) { node.left = lchild; tree.add(node.left); } // 建右子树 rchild = rightchild(node, count, bitree); if (rchild != null) { node.right = rchild; tree.add(node.right); } } else { // node = new TreeNode(Integer.parseInt(str)); node = tree.get(count - 1); // 建左子树 lchild = leftchild(node, count, bitree); if (lchild != null) { node.left = lchild; tree.add(node.left); } // 建右子树 rchild = rightchild(node, count, bitree); if (rchild != null) { node.right = rchild; tree.add(node.right); } } } } return root; } // 建某个节点的做左孩子 public TreeNode leftchild(TreeNode node, int count, String[] bitree) { int len = bitree.length; TreeNode lchild = null; if (2 * count > len) return null; else { if (!bitree[2 * count - 1].equals("#")) { lchild = new TreeNode(Integer.parseInt(bitree[2 * count - 1])); } } return lchild; } // 建某个节点的右子树 public TreeNode rightchild(TreeNode node, int count, String[] bitree) { int len = bitree.length; TreeNode rchild = null; if (2 * count + 1 > len) return null; else { if (!bitree[2 * count].equals("#")) { rchild = new TreeNode(Integer.parseInt(bitree[2 * count])); } } return rchild; } // 先序遍历二叉树（采用递归的方式） public ArrayList
preorderTraversal(TreeNode root) { ArrayList
list = new ArrayList
(); if (root == null) return list; if (root != null) list.add(root.val); if (root.left != null) list.addAll(preorderTraversal(root.left)); if (root.right != null) list.addAll(preorderTraversal(root.right)); return list; } // 先序遍历二叉树(采用栈的方式) public ArrayList
preorderTraversal2(TreeNode root) { // LinkedList
bitree = new LinkedList
(); Stack
stack = new Stack
(); ArrayList
list = new ArrayList
(); if (root == null) return list; if (root != null) { stack.push(root); list.add(root.val); root.isRead = true; } else return null; while (stack.size() > 0) { if (root.left != null && root.left.isRead == false) { root.left.isRead = true; stack.push(root.left); list.add(root.left.val); root = root.left; } else if (root.right != null && root.right.isRead == false) { root.right.isRead = true; stack.push(root.right); list.add(root.right.val); root = root.right; } else { stack.pop(); // System.out.println(bitree.size()); // System.out.print(bitree.getLast().val+"*"); if (stack.size() > 0) root = stack.peek(); } } return list; } // 先序遍历二叉树 public void pre(TreeNode root) { if (root != null) { System.out.print(root.val + " "); pre(root.left); pre(root.right); } } // 中序遍历二叉树（采用递归的方式） public ArrayList
midorderTraversal(TreeNode root) { ArrayList
list = new ArrayList
(); if (root == null) return list; if (root.left != null) list.addAll(midorderTraversal(root.left)); if (root != null) list.add(root.val); if (root.right != null) list.addAll(midorderTraversal(root.right)); return list; } // 后序遍历二叉树（采用