【697】力扣中的二叉树 based on python
2022/5/2 12:42:43
本文主要是介绍【697】力扣中的二叉树 based on python,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二叉树算是比较难得数据结构,相对于常见的数据结构而言更加抽象,本文主要是针对力扣中相关二叉树的问题进行说明,也是因为自己在做题中来逐渐学习和复习的过程!
首先几点说明如下:
-
判断是否存在根节点,可以直接 if root: ,也可以通过赋值来判断 if root == None: 以及 if root is None: 。
-
对于题目中给出的输入数据以数组形式显示,这个不用理会具体是通过怎样的遍历方式显示的,跟具体的解题没有关系,只是显示而已,具体的解题还是完全根据二叉树本身的结构和性质来实现!
-
针对二叉树的操作,需要多次运用到递归的思想,一个问题可能用到两次递归都是有可能的。
-
另外,可以通过 print 来调试程序,选择“执行代码”的时候也会打印出对应的信息,因为针对二叉树的问题,不容易在本地IDE上面处理,因为需要创建二叉树,不像数组那么简单!
1. #94 二叉树的中序遍历
二叉树的主要遍历就是
-
先序遍历
-
中序遍历
-
后序遍历
-
层次遍历
主要思想就是递归,设置一个出口!
# 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]: if root is None: return [] list_left = Solution.inorderTraversal(self, root.left) list_middle = [root.val] list_right = Solution.inorderTraversal(self, root.right) return list_left + list_middle + list_right
2. #100. 相同的树
直接判断它们的遍历结果是否一致,为了区分不同方向的树,需要添加叶子节点的左右子树的信息。
# 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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool: p_list = Solution.preOrderTraverse(self, p) q_list = Solution.preOrderTraverse(self, q) if p_list == q_list: return True else: return False def preOrderTraverse(self, tn: TreeNode) -> list: if tn is None: return [0] # 用来记录空树的信息 middle_list = [tn.val] left_list = Solution.preOrderTraverse(self, tn.left) right_list = Solution.preOrderTraverse(self, tn.right) return middle_list + left_list + right_list
3. #101. 对称二叉树
考虑 先序遍历 与 后序遍历 正好相反来构建算法
# 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 isSymmetric(self, root: Optional[TreeNode]) -> bool: if root and root.left == None and root.right == None: return True if root.left and root.right == None or root.left == None and root.right: return False pre_list = Solution.preOrderTraverse(self, root) post_list = Solution.postOrderTraverse(self, root) if pre_list == post_list[::-1]: return True else: return False def preOrderTraverse(self, root: TreeNode): if root is None: return [0] left_list = Solution.preOrderTraverse(self, root.left) middle_list = [root.val] right_list = Solution.preOrderTraverse(self, root.right) return middle_list + left_list + right_list def postOrderTraverse(self, root: TreeNode): if root is None: return [0] left_list = Solution.postOrderTraverse(self, root.left) middle_list = [root.val] right_list = Solution.postOrderTraverse(self, root.right) return left_list + right_list + middle_list def midOrderTraverse(self, root: TreeNode): if root is None: return [0] left_list = Solution.midOrderTraverse(self, root.left) middle_list = [root.val] right_list = Solution.midOrderTraverse(self, root.right) return left_list + middle_list + right_list
4. #104. 二叉树的最大深度
直接递归就行了!
# 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 maxDepth(self, root: Optional[TreeNode]) -> int: if root is None: return 0 return max(Solution.maxDepth(self, root.left), Solution.maxDepth(self, root.right)) + 1
5. #
这篇关于【697】力扣中的二叉树 based on python的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python