# Binary Tree Inorder Traversal — leetcode

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?

/**
* Definition for binary tree
* 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> ans;
stack<TreeNode *> s;
while (!s.empty() || root) {
while (root) {
s.push(root);
root = root->left;
}

root = s.top();
s.pop();
ans.push_back(root->val);
root = root->right;
}
return ans;
}
};

vector<int> inorderTraversal(TreeNode *root) {
vector<int> ans;
stack<TreeNode *> s;
while (!s.empty() || root) {
if (root) {
s.push(root);
root = root->left;
}
else {
root = s.top();
s.pop();
ans.push_back(root->val);
root = root->right;
}
}
return ans;
}

vector<int> inorderTraversal(TreeNode *root) {
vector<int> ans;
while (root) {
if (!root->left) {
ans.push_back(root->val);
root = root->right;
}
else {
TreeNode *rightMost = root->left;
while (rightMost->right && rightMost->right != root)
rightMost = rightMost->right;

if (!rightMost->right) {
rightMost->right = root;
root = root->left;
}
else {
ans.push_back(root->val);
rightMost->right = 0;
root = root->right;
}
}
}
return ans;
}

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，您必须在下载后24小时内删除！
3. 不得使用于非法商业用途，不得违反国家法律。否则后果自负！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 本站源码并不保证全部能正常使用，仅供有技术基础的人学习研究，请谨慎下载
8. 如遇到加密压缩包，请使用WINRAR解压,如遇到无法解压的请联系管理员！

### 1 评论

1. I really love to read such an excellent article. Helpful article. Hello Administ . Metropol Halı Karaca Halı Öztekin ve Selçuklu Halı Cami Halısı ve Cami Halıları Türkiye’nin En Büyük Cami Halısı Fabrikasıyız…