[LintCode] 二叉树的中序遍历
2024-09-16 03:09:49
The recursive solution is trivial and I omit it here.
Iterative Solution using Stack (O(n) time and O(n) space):
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
/**
* @param root: The root of binary tree.
* @return: Inorder in vector which contains node values.
*/
public:
vector<int> inorderTraversal(TreeNode *root) {
// write your code here
vector<int> nodes;
TreeNode* node = root;
stack<TreeNode*> toVisit;
while (node || !toVisit.empty()) {
if (node) {
toVisit.push(node);
node = node -> left;
}
else {
node = toVisit.top();
toVisit.pop();
nodes.push_back(node -> val);
node = node -> right;
}
}
return nodes;
}
};
Another more sophisticated soltuion using Morris Traversal (O(n) time and O(1) space):
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
/**
* @param root: The root of binary tree.
* @return: Inorder in vector which contains node values.
*/
public:
vector<int> inorderTraversal(TreeNode *root) {
// write your code here
vector<int> nodes;
TreeNode* node = root;
while (node) {
if (node -> left) {
TreeNode* predecessor = node -> left;
while (predecessor -> right && predecessor -> right != node)
predecessor = predecessor -> right;
if (!(predecessor -> right)) {
predecessor -> right = node;
node = node -> left;
}
else {
predecessor -> right = NULL;
nodes.push_back(node -> val);
node = node -> right;
}
}
else {
nodes.push_back(node -> val);
node = node -> right;
}
}
return nodes;
}
};
最新文章
- IO流基本操作
- js 验证用户名和密码是否为空
- Python学习笔记——Day1
- jsckson,想说爱你不容易啊。。。406错误
- MyCat 学习笔记 第八篇.数据分片 之 求摸运算分片
- poj 2312 Battle City
- 用C++ 设计一个不能被继承的类
- asp.net Handler中的IsReusable属性及在Handler中使用Session
- 学习笔记 一步步了解webpack
- Spark学习之Spark Streaming
- cdh集群认证命令
- 时序扩展的UML状态图的测试用例生成研究
- flask 定义数据库关系（一对一）
- JavaScript学习（一）
- 使用.NET向webService传double、int、DateTime 服务器得到的数据时null的问题(转http://blog.csdn.net/slimboy123/article/details/4366701)
- QT5下的caffe项目属性
- 单字段去重 distinct 返回其他多个字段
- 批量删除进程清理 minerd
- Python实现创建字典
- ImportError: No module named Crypto.PublicKey