首页 > 代码库 > [LeetCode] Binary Tree Preorder Traversal
[LeetCode] 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 / 3
return [1,2,3]
.
Note: Recursive solution is trivial, could you do it iteratively?
这题简单,属于课本习题的难度,题目提示说用迭代试试,当然用递归也可以AC的。迭代的时候要注意栈的性质,不要push反了。
void preorderIter2(TreeNode *node, stack<TreeNode*>&st, vector<int>&ret) { while (!st.empty()) { TreeNode *top = st.top(); st.pop(); ret.push_back(top->val); if (top->right) st.push(top->right); if (top->left) st.push(top->left); }}vector<int> preorderTraversal(TreeNode *root) { vector<int> ret; if (!root) return ret; stack<TreeNode *> st; st.push(root); preorderIter2(root, st, ret); return ret;}
迭代版
void preorderIter(TreeNode *node, vector<int> &ret) { if (!node) return; ret.push_back(node->val); cout << node->val <<endl; preorderIter(node->left, ret); preorderIter(node->right, ret);}
[LeetCode] Binary Tree Preorder Traversal
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。