Binary Tree Inorder Traversal !!!!!!!!!!!!!!!!!!!!!!!! 迭代的方法要仔细体会

Q:
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

A:

-----用stack迭代  ， 每个节点pop出来的时候，才去visit， 入栈时走左边，出栈后，走右边
又是双100%, LOL

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        vector<TreeNode*> stack;
        while(root || !stack.empty()){
            if(root){
                stack.push_back(root);
                root=root->left;         
            }else{
                root = stack.back();
                stack.pop_back();
                res.push_back(root->val);
                root = root->right;
            }
        }
        return res;
    }
};

Learned:
1：  in-order iterative traversal的关键点是两个：
       1）  把左节点先都加进去， 然后， 一个个地弄出来，visit + 考虑右子树
       2）  在循环的时候，并不是每次都pop，
       3） 通过curNode 是否为null来标记 当前我们是否走到了right节点的最下边，不是的话，就要重新考虑其左右子节点。 (或者说，标记是否刚刚走的是right 节点）