面試中經(jīng)常會考的一道題目，就是二叉樹的遍歷，很簡單，你會說“使用遞歸，根據(jù)要求（前序、中序、后序，以中序為例）依次對節(jié)點和其左右子節(jié)點調(diào)用遞歸方法。

public void printNode(Node node) {
    if (null != node.left)
        printNode(node.lef);
    System.out.print(node.toString());
    if(null != node.right)
        printNode(node.right);
    }

一般還會繼續(xù)追問"能否使用非遞歸的方法?"，在美團點評面試的時候就被問到了(同LeetCode 144)。這時候，我們可以使用棧來完成，分為下面三個步驟：

1. 深度遍歷找到這棵樹最左邊的節(jié)點，這個過程中將遍歷的節(jié)點壓入棧中。
2. 將棧中的節(jié)點pop出來，如果該節(jié)點有右子節(jié)點，對右子節(jié)點進(jìn)行步驟一的操作，如果沒有，則可以打印出來，繼續(xù)pop棧。
3. 當(dāng)棧空了或者進(jìn)行操作的根節(jié)點為空時推出循環(huán)。
   下面就用代碼來實現(xiàn)一下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; 
    }
}