Binary Tree Inorder Traversal（C++ code）

LeetCode Binary Tree Inorder Traversal， Aug 27 '12
Given a binary tree, return the inorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

先来个recursion的：

void doinorder(TreeNode *root, vector<int> & res){
  if (root == NULL) return;
  doinorder(root->left, res);
  res.push_back(root->val);
  doinorder(root->right, res);
} 

vector<int> inorderTraversal(TreeNode *root){
  vector<int> res; 

  if(root == NULL)  return res;
  
  doinorder(root,  res);
  
  return res;
}

然后是iterative的：

vector<int> inorderTraversal(TreeNode *root){
  vector<int> res; 

  stack<TreeNode *> stk;
  if(root == NULL)  return res;
 
  while(!stk.empty()|| root){
    while(root != NULL) {
       stk.push(root);
       root = root->left;
     }
    root = stk.top();
    stk.pop();
    res.push_back(root->val);
    root = root->right;
   
  }
  
  return res;
}

Further reading:
http://en.wikipedia.org/wiki/Threaded_binary_tree