文章目录
1. 题目信息2. 解题2.1 递归2.2 循环,必须掌握1. 题目信息
给定一个二叉树,返回它的 前序 遍历。
示例:输入: [1,null,2,3] 1\2/3 输出: [1,2,3]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
来源:力扣(LeetCode)
链接:https://leetcode-/problems/binary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
2. 解题
2.1 递归
class Solution {public:vector<int> preorderTraversal(TreeNode* root) {vector<int> ans;preorder(root, ans);return ans;}void preorder(TreeNode* root, vector<int> &ans){if(root == NULL)return;ans.push_back(root->val);preorder(root->left, ans);preorder(root->right, ans);}};
2.2 循环,必须掌握
根左右
class Solution {public:vector<int> preorderTraversal(TreeNode* root) {vector<int> ans;stack<TreeNode*> stk;while(root || !stk.empty()){while(root){stk.push(root);ans.push_back(root->val);root = root->left;}root = stk.top()->right;stk.pop();}return ans;}};