首页 > 代码库 > Binary Tree Inorder Traversal
Binary Tree Inorder Traversal
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; }};
Binary Tree Inorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。