LeetCode 144. 二叉树的前序遍历（前序遍历）

文章目录

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;}};