首页 > 代码库 > LintCode 二叉树的中序遍历
LintCode 二叉树的中序遍历
给出一棵二叉树,返回其中序遍历
样例
给出二叉树 {1,#,2,3}
,
1 2 / 3
返回 [1,3,2]
.
挑战
你能使用非递归算法来实现么?
分析:同前序遍历。
/** * 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 TreeNode *curr=root; stack<TreeNode *> mystack; vector<int> res; while(!mystack.empty()||curr!=NULL) { while(curr!=NULL) { mystack.push(curr); curr=curr->left; } if(!mystack.empty()) { curr=mystack.top(); res.push_back(curr->val); mystack.pop(); curr=curr->right; } } return res; } };
用数组指针
/** * 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 TreeNode *curr=root; TreeNode *mystack[1000]; int top=0; vector<int> res; while(top!=0||curr!=NULL) { while(curr!=NULL) { mystack[top++]=curr; curr=curr->left; } if(top>0) { top--; curr=mystack[top]; res.push_back(curr->val); curr=curr->right; } } return res; } };
LintCode 二叉树的中序遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。