一、题目描述
给定一个二叉树，返回它的前序遍历结果。
例如输入二叉树 [1,null,2,3]：
|
1 2 3 4 5 |
1 \ 2 / 3 |
输出：
|
1 |
[1,2,3] |
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
二、题解
二叉树的前序遍历，递归和非递归方式。
参考：二叉树的前序遍历。
三、代码
3.1 递归代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { void preorderTraversal(TreeNode *root, vector<int> &v) { if (root == nullptr) { return; } v.push_back(root->val); if (root->left) { preorderTraversal(root->left, v); } if (root->right) { preorderTraversal(root->right, v); } } public: vector<int> preorderTraversal(TreeNode* root) { vector<int> v; preorderTraversal(root, v); return v; } }; |
3.2 非递归代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Solution { public: vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode *> st; TreeNode *p; vector<int> v; p = root; while (p || !st.empty()) { while (p) { // 遍历当前节点 v.push_back(p->val); st.push(p); // 遍历左子树 p = p->left; } // 通过栈来遍历右子树 if (!st.empty()) { p = st.top()->right; st.pop(); } } return v; } }; |
