首页 > 代码库 > 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?
思路:使用栈模拟递归过程。以下是网上看到的非常简洁的解法:(若当前节点的左儿子存在,则将左儿子入栈。这样保证了每次从栈顶取出元素时,已经完成了对该元素左子树的访问)
1 class Solution { 2 public: 3 vector<int> inorderTraversal( TreeNode *root ) { 4 vector<int> values; 5 stack<TreeNode*> nodeStack; 6 TreeNode *node = root; 7 while( !nodeStack.empty() || node ) { 8 if( node ) { 9 nodeStack.push( node );10 node = node->left;11 } else {12 node = nodeStack.top();13 nodeStack.pop();14 values.push_back( node->val );15 node = node->right;16 }17 }18 return values;19 }20 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。