94. Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

Follow up: Recursive solution is trivial, could you do it iteratively?

---

本题要实现二叉树的中序遍历。这个题应该是很基本的二叉树的遍历题，本科学数据结构对这个是基本要求。不过本科学的是中文教材，只知道前序、中序、后序，不知道对应的英文是什么，WIKI上的Tree traversal图解还是很通俗易懂的：前序（Pre-order），中序（In-order），后序（Post-order）和层次遍历（Level-order）。
前序、中序和后序的区别很容易记，只要记住他们的前、中、后分别是访问根节点的顺序。比如前序顺序是先访问根节点，然后依次访问左右孩子节点。前序：根左右；中序：左根右；后序：左右根。
本题要实现二叉树的中序遍历，如上所述，先访问左子树，然后访问根节点，最后访问右子树。用递归的方法非常简洁直观。递归的完整代码如下：

class Solution {
public:
    void work(vector<int>& ans, TreeNode* root)
    {
        if (root == NULL)
            return;
        work(ans, root->left); // 左
        ans.push_back(root->val); // 根
        work(ans, root->right); // 右
    }
    vector<int> inorderTraversal(TreeNode* root)
    {
        vector<int> ans;
        work(ans, root);
        return ans;
    }
};

本代码提交AC，用时0MS。

但是Note问能不能用迭代实现以下呢？当然可以，所以可以用递归实现的算法肯定都可以用迭代的方法实现，只是有时候迭代写起来更麻烦。
我的思路是肯定要首先找到树的最左下角的叶子节点，这个节点是最先被访问的，然后访问根节点，最后访问右子树。访问右子树的时候，又是重复之前的操作，首先找到右子树中的最左下角的叶子节点，访问它，然后访问根节点，最后又访问其右子树。
上述过程需要在访问完左孩子之后再访问根节点，但是树中节点的指向是单向的，只能由根访问到孩子，不能由孩子回溯到根。我们不可能在找孩子的同时保存该孩子的父亲节点，这样太麻烦了。于是我想到了用堆栈，在找最左下角的叶子节点的时候，顺便把经过的祖先节点压到堆栈中，当访问完孩子节点后，弹栈，此时的栈顶节点就是父亲节点了。如果父节点有右子树，则进入右子树，重复之前的过程（找右子树的最左下角叶子）。
迭代法的完整代码如下：

class Solution {
public:
    void putAllLeft(TreeNode* root, stack<TreeNode*>& tree)
    {
        while (root != NULL) {
            tree.push(root);
            root = root->left;
        }
    }
    vector<int> inorderTraversal(TreeNode* root)
    {
        vector<int> ans;
        stack<TreeNode*> tree;
        putAllLeft(root, tree); // 找最左边的叶子节点
        TreeNode* top;
        while (!tree.empty()) {
            top = tree.top();
            ans.push_back(top->val); // 访问左（根）节点
            tree.pop();
            putAllLeft(top->right, tree); // 访问右节点
        }
        return ans;
    }
};

本代码提交AC，用时0MS。
调试的时候可以使用我之前写过的由数组生成二叉树的函数，挺方便的。