二叉树的非递归前序遍历，大抵是很多人信手拈来、不屑一顾的题目罢。然而因为本人记性不好、基础太差的缘故，做这道题的时候居然自己琢磨出了一种解法，虽然谈不上创新，但简单一搜也未发现雷同，权且记录，希望于人于己皆有帮助。
估计能看到这里的读者，都是见过题目的，但还是链接原题在此：Binary Tree Preorder Traversal
二话不说，直接上代码：
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public ArrayList<Integer> preorderTraversal(TreeNode root) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
ArrayList<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
} TreeNode curr = root;
Stack<TreeNode> rights = new Stack<TreeNode>();
while (curr != null) {
res.add(curr.val);
if (curr.right != null) {
rights.push(curr.right);
}
curr = curr.left;
if (curr == null && !rights.empty()) {
curr = rights.pop();
}
} return res;
}
}
一次过，372 ms，C++ 大牛勿笑。。。Java 大牛也包涵。。。
做出来之后想搜搜有木有（基本上肯定有）更高级的解法，于是发现了教科书一般的景象。。。无论是 C++ 还是 Java，代码总有相同的一处，就是根节点入栈，出栈之后再判断左右孩子是否为空。本人猜想这一定是某本或者某些教科书里的标准解法，被大家铭记在心了。
教科书解法或许更有教学意义，或许更普适通用，但本人的小解法，用来对付这道题已经足够。
前序遍历只需保存当前节点的右孩子，当前节点不用在栈里打个来回，直接痛快把自己的值交出来，然后把皇位让给左孩子便是了~
不过后面一道后序遍历的还木有做出来。。。继续努力！
大家光棍成双节快乐！