首页 > 代码库 > Leetcode: Binary Tree Inorder Traversal
Leetcode: 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?
分析：迭代版inorder traversal。对于任何一棵树，其最先被访问的是路径是最左侧的路径，在该最左侧路径上访问顺序呢是从叶子结点到根节点，很自然我们可以用一个stack保存这个路径。同时如果当前访问结点有右孩子，我们需把以右孩子为根的子树最左路径压入栈中。时间复杂度为O(n)，空间复杂度为O(h)。代码如下：
1 class Solution { 2 public: 3 vector<int> inorderTraversal(TreeNode *root) { 4 vector<int> result; 5 if(!root) return result; 6 7 stack<TreeNode*> S; 8 for(TreeNode *p = root; p; p = p->left) 9 S.push(p);10 11 while(!S.empty()){12 TreeNode *tmp = S.top();13 S.pop();14 result.push_back(tmp->val);15 for(TreeNode *p = tmp->right; p ; p = p->left)16 S.push(p);17 }18 19 return result;20 }21 };
Leetcode: Binary Tree Inorder Traversal
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。