Binary Tree Inorder Traversal

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

For example:

Given binary tree {1,#,2,3},

   12/3

 

return [1,3,2].

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

中序遍历非递归版本

法一：

class Solution {
private:vector<int> res;
public:vector<int> inorderTraversal(TreeNode *root) {res.clear();if(root==NULL) return res;stackbool>> s;s.push(make_pair(root,false));while (!s.empty()){root=s.top().first;while (root!=NULL&&!s.top().second){s.top().second=true;root=root->left;if(root!=NULL) s.push(make_pair(root,false));}root=s.top().first->right;res.push_back(s.top().first->val);s.pop();if(root!=NULL)s.push(make_pair(root,false));}return res;}
};

 

法二：

class Solution {
private:vector<int> res;
public:vector<int> inorderTraversal(TreeNode *root) {res.clear();if(root==NULL) return res;stackbool>> s;TreeNode* t;int used;s.push(make_pair(root,false));while(!s.empty()){t=s.top().first;used = s.top().second;s.pop();if(!used){if(t->right!=NULL) s.push( make_pair(t->right,false));s.push(make_pair(t,true));if(t->left!=NULL) s.push( make_pair(t->left,false));}else res.push_back(t->val);}return res;}
};