654. 最大二叉树 - 力扣（LeetCode）

image.png

# 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 constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        max_num = max(nums)
        max_index = nums.index(max_num)
        node = TreeNode(val=max_num)

        node.left = self.constructMaximumBinaryTree(nums[:max_index])
        node.right = self.constructMaximumBinaryTree(nums[max_index+1:])

        return node

• 递归要有变量接return

617. 合并二叉树 - 力扣（LeetCode）

image.png

# 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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if root1 == None: return root2
        if root2 == None: return root1

        root1.val += root2.val

        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)

        return root1

700. 二叉搜索树中的搜索 - 力扣（LeetCode）

image.png

解题思路

注意是二叉搜索树

# 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 searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        while root:
            if root.val > val:
                root = root.left
            elif root.val < val:
                root = root.right
            else:
                return root
        return None

# 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 searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root or root.val == val:
            return root

        if root.val < val:
            result = self.searchBST(root.right, val)
        if root.val > val:
            result = self.searchBST(root.left, val)

        return result

98. 验证二叉搜索树 - 力扣（LeetCode）

image.png

解题思路

利用中序遍历，如果是二叉搜索树，遍历结果应该是单调递增的

# 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 __init__(self):
        self.max_value = float('-inf')

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root == None:
            return True

        left_bool = self.isValidBST(root.left)

        if root.val > self.max_value:
            self.max_value = root.val
        else:
            return False

        right_bool = self.isValidBST(root.right)

        return left_bool&right_bool

# 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
#  中序遍历就是递增序列了，利用双指针，避免第一个节点值就是float最小值
class Solution:
    def __init__(self):
        self.pre = TreeNode(val=None)

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root == None:
            return True

        left_bool = self.isValidBST(root.left)

        if self.pre.val != None and root.val <= self.pre.val:
            return False
        self.pre = root

        right_bool = self.isValidBST(root.right)

        return left_bool&right_bool

• 注意两种不同方法中 ‘中’的条件判断的不同