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].

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;stack<pair<TreeNode*,bool>> 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;stack<pair<TreeNode*,bool>> 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;} };

?

轉(zhuǎn)載于:https://www.cnblogs.com/fightformylife/p/4244454.html

總結(jié)

以上是生活随笔為你收集整理的Binary Tree Inorder Traversal的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。