题目链接

二叉树的前序遍历：按照访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。

Python3

方法一： 递归 $⟮O(n)⟯$

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:""" 前序遍历 [ 根 左子树 右子树 ]  递归"""def preorder(node):if not node:return ans.append(node.val)preorder(node.left)preorder(node.right)ans = []preorder(root)return ans        

方法二： 迭代 $⟮O(n)⟯$

递归：隐式地维护了一个栈
迭代：显式地将这个栈模拟出来

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:""" 前序遍历 [根 左子树  右子树]  迭代"""ans =[]stack = []cur = rootwhile cur or stack:while cur:ans.append(cur.val)  # 根 加入 ans  stack.append(cur)  cur = cur.left  # 左cur = stack.pop() cur = cur.right  # 右return ans 

方法三： Morris $⟮O(n)、O(1)⟯$

参考链接

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:""" 前序遍历 [根 左子树 右子树 ]  Morris  O(N) O(1)"""ans = []cur, pre = root, None while cur:if not cur.left:ans.append(cur.val) ##cur = cur.right # 有左孩子else:# 找 pre pre = cur.left while pre.right and pre.right != cur:pre = pre.right  if not pre.right: ## 找到 mostrightpre.right = curans.append(cur.val) ## 前序遍历cur = cur.left else:pre.right = None # ans.append(cur.val)  中序遍历cur = cur.right return ans 

C++

方法一： 递归 $⟮O(n)⟯$

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:// 子 模块 void preorder(TreeNode *node, vector<int> &ans){if (node == nullptr){return; }ans.emplace_back(node->val);preorder(node->left, ans);preorder(node->right, ans);}// 主模块vector<int> preorderTraversal(TreeNode* root) {vector<int> ans;preorder(root, ans);return ans;}
};

方法二： 迭代 $⟮O(n)⟯$

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> ans;if (root == nullptr){return ans;}stack<TreeNode*> stk;  // 栈 的定义TreeNode* cur = root;while (cur != nullptr || !stk.empty()){while (cur != nullptr){ans.emplace_back(cur->val); // 根stk.emplace(cur);  //  入栈cur = cur->left; // 左}// 开始 栈 弹出cur = stk.top(); // 取 栈顶元素stk.pop();    // 不返回 值   cur = cur->right; // 右}   return ans;}
};

stack 类

stack 类 文档链接

Python3 的 list 会返回
文档

lis = [1, 2, 3, 4]
print(lis.pop())

方法三： Morris $⟮O(n)、O(1)⟯$

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int> ans;TreeNode* cur = root;TreeNode* pre = nullptr;while (cur != nullptr){if (cur->left == nullptr){ // 情况1ans.emplace_back(cur->val);cur = cur->right;}else{// 有左孩子  // 情况 2// 找 pre pre = cur->left;while (pre->right != nullptr && pre->right != cur){pre = pre->right;}if (pre->right == nullptr){ // 情况 2(1)pre->right = cur;ans.emplace_back(cur->val);cur = cur->left;}else{  // 情况 2(2)pre->right = nullptr;cur = cur -> right;}}}return ans;}
};