首页 > 代码库 > 二叉树的中序遍历
二叉树的中序遍历
二叉树的中序遍历
给出一棵二叉树,返回其中序遍历
样例
给出二叉树 {1,#,2,3}
,
1 2 / 3
返回 [1,3,2]
.
挑战
你能使用非递归算法来实现么?
标签
递归 二叉树 二叉树遍历
1 /** 2 * Definition of TreeNode: 3 * class TreeNode { 4 * public: 5 * int val; 6 * TreeNode *left, *right; 7 * TreeNode(int val) { 8 * this->val = val; 9 * this->left = this->right = NULL; 10 * } 11 * } 12 */ 13 class Solution { 14 /** 15 * @param root: The root of binary tree. 16 * @return: Inorder in vector which contains node values. 17 */ 18 public: 19 vector<int> inorderTraversal(TreeNode *root) { 20 // write your code here 21 vector<int> order; 22 if(root == NULL) 23 return order; 24 25 stack<TreeNode*> s; 26 TreeNode *p=root; 27 while(p!=NULL||!s.empty()) { 28 while(p!=NULL) { 29 s.push(p); 30 p=p->left; 31 } 32 if(!s.empty()) { 33 p=s.top(); 34 order.push_back(p->val); 35 s.pop(); 36 p=p->right; 37 } 38 } 39 return order; 40 } 41 };
二叉树的中序遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。