因酷网站建设,网站设计制作哪些,网站建设包装策略,未来的软件开发方向是什么文章目录前序遍历代码\Python代码\C中序遍历代码\Python代码\C后序遍历代码\Python代码\C层序遍历代码\Python代码\C反向层序遍历代码\Python代码\C总结前序遍历
题目链接 前序遍历意思就是按照“根节点-左子树-右子树”的顺序来遍历二叉树#xff0c;通过递归方法来实现…
文章目录前序遍历代码\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, val0, leftNone, rightNone):
# 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:vectorint preorderTraversal(TreeNode* root) {vectorint res;travel(root, res);return res;}void travel(TreeNode *root, vectorint 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, val0, leftNone, rightNone):
# 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:vectorint inorderTraversal(TreeNode* root) {vectorint res;inorder(root, res);return res;}void inorder(TreeNode *root, vectorint 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, val0, leftNone, rightNone):
# 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:vectorint postorderTraversal(TreeNode* root) {vectorint res;postorder(root, res);return res;}void postorder(TreeNode *root, vectorint 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, val0, leftNone, rightNone):
# 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:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint res;travel(root, 0, res);return res;}void travel(TreeNode *root, int depth, vectorvectorint 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种二叉树的遍历方式也是二叉树很多题目的基础算法如果对你有帮助的话动动手指点个赞吧
