面试中经常会考的一道题目，就是二叉树的遍历，很简单，你会说“使用递归，根据要求（前序、中序、后序，以中序为例）依次对节点和其左右子节点调用递归方法。
public void printNode(Node node) {
if (null != node.left)
printNode(node.lef);
System.out.print(node.toString());
if(null != node.right)
printNode(node.right);
}
一般还会继续追问"能否使用非递归的方法?"，在美团点评面试的时候就被问到了(同LeetCode 144)。这时候，我们可以使用栈来完成，分为下面三个步骤：
- 深度遍历找到这棵树最左边的节点，这个过程中将遍历的节点压入栈中。
- 将栈中的节点pop出来，如果该节点有右子节点，对右子节点进行步骤一的操作，如果没有，则可以打印出来，继续pop栈。
- 当栈空了或者进行操作的根节点为空时推出循环。
下面就用代码来实现一下LeetCode 144
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
ArrayList<Integer> result = new ArrayList<>();
if (null == root) {
return null;
}
Stack<TreeNode> nodeStack = new Stack<>();
TreeNode temp = root;
while (null != temp || !nodeStack.empty()) {
nodeStack.push(temp);
result.add(temp.val);
while (null != temp.left) {
temp = temp.left;
nodeStack.push(temp);
result.add(temp.val);
}
while (!nodeStack.empty() && null == nodeStack.peek().right) {
nodeStack.pop();
}
if (nodeStack.empty())
break;
temp = nodeStack.pop();
if (null != temp.right) {
temp = temp.right;
continue;
}
}
return result;
}
}
