首页 > 代码库 > Binary Tree Preorder Traversal
Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes‘ values.
For example:
Given binary tree {1,#,2,3},
1 2 / 3return [1,2,3].
Note: Recursive solution is trivial, could you do it iteratively?
思路：取栈顶元素，输出该元素并将其出栈；若其右子树不空，将右子节点入栈；若其左子树不空，将左子节点入栈。循环直到栈为空。
1 class Solution { 2 public: 3 vector<int> preorderTraversal( TreeNode *root ) { 4 vector<int> result; 5 if( !root ) { return result; } 6 stack<TreeNode*> nodesStack; 7 nodesStack.push( root ); 8 while( !nodesStack.empty() ) { 9 TreeNode* curr = nodesStack.top();10 nodesStack.pop();11 result.push_back( curr->val );12 if( curr->right ) { nodesStack.push( curr->right ); }13 if( curr->left ) { nodesStack.push( curr->left ); }14 }15 return result;16 }17 };
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。