网站建设旗舰品牌上海短视频推广
文章目录
- 前序遍历
- 代码\Python
- 代码\C++
- 中序遍历
- 代码\Python
- 代码\C++
- 后序遍历
- 代码\Python
- 代码\C++
- 层序遍历
- 代码\Python
- 代码\C++
- 反向层序遍历
- 代码\Python
- 代码\C++
- 总结
前序遍历
题目链接
前序遍历意思就是按照“根节点-左子树-右子树”的顺序来遍历二叉树，通过递归方法来实现的话很简单，我们只需要描述一下访问的规则：
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种二叉树的遍历方式，也是二叉树很多题目的基础算法，如果对你有帮助的话，动动手指点个赞吧！