算法第十七天｜654. 最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

654. 最大二叉树

题目

思路与解法

# 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_val = max(nums)
        max_idx = nums.index(max_val)
        root = TreeNode(max_val)
        root.left = self.constructMaximumBinaryTree(nums[:max_idx])
        root.right = self.constructMaximumBinaryTree(nums[max_idx+1:])
        return root

617.合并二叉树

题目

思路与解法

第一想法： 通过层序遍历来合并
一遍过，哈哈，虽然肯定有可以优化的地方

# 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 not root1:
            return root2
        if not root2:
            return root1

        from collections import deque
        queue1 = deque()
        queue2 = deque()
        queue1.append(root1)
        queue2.append(root2)
        while queue1 or queue2:
            cur1 = queue1.popleft()
            cur2 = queue2.popleft()
            cur_new_val = cur1.val + cur2.val
            cur1.val = cur_new_val
            if not cur1.left and cur2.left:
                cur1.left = TreeNode(0)
            elif cur1.left and not cur2.left:
                cur2.left = TreeNode(0)
            if not cur1.right and cur2.right:
                cur1.right = TreeNode(0)
            elif cur1.right and not cur2.right:
                cur2.right = TreeNode(0)
            if cur1.left:
                queue1.append(cur1.left)
                queue2.append(cur2.left)
            if cur1.right:
                queue1.append(cur1.right)
                queue2.append(cur2.right)
            
        return root1

700.二叉搜索树中的搜索

题目

思路与解法

第一想法：

# 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]:
        val_node = self.find_root(root, val)
        return val_node


    def find_root(self, node, val):
        if not node:
            return None
        if node.val == val:
            return node
        elif node.val > val:
            return self.find_root(node.left, val)
        elif node.val < val:
            return self.find_root(node.right, val)

98.验证二叉搜索树

题目

思路与解法

第一想法： 判断每个结点作为root结点构成的子树是不是二叉搜索树，如下。但是有坑，光判断每个子数是不够的，因为子树中结点可能不满足子树外的条件

# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
            
        if root.left and root.left.val >= root.val:
            return False

        if root.right and root.right.val <= root.val:
            return False
        return self.isValidBST(root.left) and self.isValidBST(root.right)

如下就不满足条件，

思考后的想法： 中序遍历后，挨个判断是不是递增的。发现carl也是这么做的，只是他有几种方法。

# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:
        self.nodes = []
        self.traversal(root)
        for i in range(len(self.nodes)-1):
            if self.nodes[i] >= self.nodes[i+1]:
                return False
        return True


    def traversal(self, root):
        if not root:
            return None
        self.traversal(root.left)
        self.nodes.append(root.val)
        self.traversal(root.right)