二叉树前中后层次遍历，递归实现

前序遍历

题目链接
  前序遍历意思就是按照“根节点-左子树-右子树”的顺序来遍历二叉树，通过递归方法来实现的话很简单，我们只需要描述一下访问的规则：

1.如果当前节点为空，就返回
2.否则就访问当前节点，
3.访问左子树（左节点）
4.访问右子树（右节点）

  对python来说，一般我们用一个列表来保存访问的结果，列表对象是可修改对象，所以我们可以直接把列表对象当做函数的参数跟着传递；对C++来说，我们可以用一个vector向量来保存结果，在函数传递时使用传引用的方式，一样可以达到效果。

代码\Python

# 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]:res = []self.preorder(root, res)return resdef preorder(self, root, res):if not root:returnres.append(root.val)self.preorder(root.left, res)self.preorder(root.right, res)

代码\C++

/*** 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> res;travel(root, res);return res;}void travel(TreeNode *root, vector<int> &res){if(!root){return;}res.push_back(root->val);travel(root->left, res);travel(root->right, res);}
};

中序遍历

题目链接
  类似的，中序遍历就是遍历的时候把根节点放到中间，即“左子树-根节点-右子树”的顺序。只需要稍微修改一下代码就行。

代码\Python

# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []self.inorder(res, root)return resdef inorder(self, res, root):if root is None:returnself.inorder(res, root.left)res.append(root.val)self.inorder(res, root.right)

代码\C++

/*** 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> inorderTraversal(TreeNode* root) {vector<int> res;inorder(root, res);return res;}void inorder(TreeNode *root, vector<int> &res){if(!root){return;}inorder(root->left, res);res.push_back(root->val);inorder(root->right, res);}
};

后序遍历

添加链接描述
  类似的，后序遍历就是遍历的时候把根节点放到最后，即“左子树-右子树-根节点”的顺序。同样只需要稍微修改一下代码就行。

代码\Python

# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []self.postorder(res, root)return resdef postorder(self, res, root):if root is None:returnself.postorder(res, root.left)self.postorder(res, root.right)res.append(root.val)

代码\C++

/*** 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> postorderTraversal(TreeNode* root) {vector<int> res;postorder(root, res);return res;}void postorder(TreeNode *root, vector<int> &res){if(!root){return;}postorder(root->left, res);postorder(root->right, res);res.push_back(root->val);}
};

层序遍历

题目链接
  层序遍历一般指对二叉树进行从上到下从左到右的一层一层的遍历，同样深度的节点在同一层。递归的层序遍历需要借助节点所在的深度信息。

代码\Python

# 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 levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:res = []self.level(root, 0, res)return resdef level(self, root, depth, res):if not root:return []if len(res) == depth:res.append([])res[depth].append(root.val)if root.left:self.level(root.left, depth + 1, res)if root.right:self.level(root.right, depth + 1, res)

代码\C++

/*** 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<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> res;travel(root, 0, res);return res;}void travel(TreeNode *root, int depth, vector<vector<int>> &res){if(!root){return;}if(res.size() == depth){res.push_back({});}res[depth].push_back(root->val);if(root->left){travel(root->left, depth + 1, res);}if(root->right){travel(root->right, depth + 1, res);}}
};

反向层序遍历

  反向层序遍历，顾名思义就是从下往上，从左往右的反着来，我们只需要在正向遍历的基础上，在最后返回答案前把答案反转一遍。

代码\Python

return res[::-1]
#or
return res.reverse()

代码\C++

reverse(res.begin(), res.end()); 
return res;

总结

  最常见最基础的4种二叉树的遍历方式，也是二叉树很多题目的基础算法，如果对你有帮助的话，动动手指点个赞吧！