[数据结构]二叉树、堆

发表于
参加Datawhale的编程计划的第5个任务，涉及二叉树、堆，用python实现。。

二叉树

练习：Invert Binary Tree（翻转二叉树）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        # method one 一个漂亮的递归（把一个复杂的问题逐步地剥开）  缺点是比较占内存
        if root:
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)   
        return root

Maximum Depth of Binary Tree（二叉树的最大深度）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxDepth(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root==None:
            return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1

Validate Binary Search Tree（验证二叉查找树）[作为可选]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root is None:
            return True
        if root.left==None and root.right==None:
            return True 
            
        self.List=[]
        self.left_root_right(root) #调用left_root_right()函数，中序遍历二叉搜索树，将节点的值存入列表List中
        for i in range(1,len(self.List)):
            if self.List[i]<=self.List[i-1]: #通过for循环遍历列表，若当前值少于或等于前一个值，则返回False
                return False
        return True 
    
    def left_root_right(self,root):
        if root==None:
            return 
        
        self.left_root_right(root.left) #中序遍历当前子树的左子树
        self.List.append(root.val) #将当前子树的根节点的值存入列表List中
        self.left_root_right(root.right)#中序遍历当前子树的右子树

堆

练习：Path Sum（路径总和）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root == None:
            return False
        if root.left == None and root.right == None:
            return root.val == sum
        if root.left == None:
            return self.hasPathSum(root.right,sum - root.val)
        if root.right == None:
            return self.hasPathSum(root.left,sum - root.val)
        return self.hasPathSum(root.left,sum - root.val) or self.hasPathSum(root.right,sum - root.val)

相关链接

编程计划的第5个任务
第五次任务 打卡表格