Leetcode94 Binary Tree Inorder T

记忆点

• 中序遍历：左中右
• 左到底再看右
• 使用stack记录结点

思路

递归的子问题与子树结构天然契合，故使用递归方法进行树的遍历非常容易。这里主要描述非递归的算法实现。
非递归思路一般是使用stack存放树的结点，以stack.empty()作为停止条件。
中序遍历的遍历顺序为左中右，所以对于每一个结点先访问左子树，直到没有左子树后，将当前结点打印，再访问当前结点的右子树。

实现

class Solution {
public:    
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ret;
        if (NULL == root) {
            return ret;
        }

        stack<TreeNode*> s;
        TreeNode* n = root;
        
        while(!s.empty() || NULL != n) {
            while (n) { // Track left tree at first
                s.push(n);
                n = n->left;
            }
            n = s.top(); // Output the node
            s.pop();
            ret.push_back(n->val);
            n = n->right; // Move to right tree
        }
        return ret;
    }
};