这个系列有preorder inorder postorder三题，考点都不是递归，而是迭代。迭代挺难想的，尤其是外面的while循环。这题的迭代写法我模仿inorder写出来了，一步步在纸上模拟入栈出栈就好了。
RECURSION:
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
return dfs(root, res);
}
private List<Integer> dfs(TreeNode root, List<Integer> res) {
if (root == null) {
return res;
}
res.add(root.val);
dfs(root.left, res);
dfs(root.right, res);
return res;
}
ITERATION:
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> res = new ArrayList<>();
Stack<TreeNode> s = new Stack<>();
while (!s.isEmpty() || root!=null) {
if (root != null) {
res.add(root.val);
s.push(root);
root = root.left;
}else {
TreeNode node = s.pop();
root = node.right;
}
}
return res;
}
看了下discussion，很多跟我写的都不一样，说明迭代写法确实比递归写法多，按照自己的思路来就好。
