Binary Tree Inorder Traversal

发布时间:2014-10-22 13:26:11编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Binary Tree Inorder Traversal",主要涉及到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? 从这道题可以总结一下二叉树遍历的方法。 方法一:递归,很直观。 public: vector<int> inorderTraversal(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<int> ret; traversal(ret,root); return ret; } void traversal(vector<int>& ret,TreeNode* root) { if(root == NULL) return; traversal(ret,root->left); ret.push_back(root->val); traversal(ret,root->right); } };20 milli secs. 方法二:迭代,需要用栈存储路径。 /** * 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) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<int> ret; stack<TreeNode*> stack; while(root != NULL || !stack.empty()) { if(root == NULL){ root = stack.top(); stack.pop(); ret.push_back(root->val); root = root->right; }else{ stack.push(root); root = root->left; } } return ret; } };20 milli secs. 方法三:以上两种方法都需要O(n)的栈空间,下面的方法能够用O(1)的空间实现遍历。 /** * 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) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<int> ret; stack<TreeNode*> stack; TreeNode* cur = root; TreeNode* prev = NULL; while(cur != NULL) { if(cur->left == NULL){ ret.push_back(cur->val); cur = cur->right; }else{ prev = cur->left; if(prev != NULL){ while(prev->right != NULL && prev->right != cur) prev = prev->right; } if(prev->right == cur){ prev->right == NULL; ret.push_back(cur->val); cur = cur->right; }else{ prev->right = cur; cur = cur->left; } } } return ret; } };


上一篇:LINUX移植——内核移植(一)
下一篇:[置顶] OGG同构(ORACLE-ORACLE)、异构(ORACLE-MYSQL)同步配置及错误解析

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款