代码随想录算法训练营第18天|654. 最大二叉树、617.合并二叉树、700. 二叉搜索树中的搜索、98.验证二叉搜索树

发布于:2024-07-11 ⋅ 阅读:(18) ⋅ 点赞:(0)

落的太多,竟然忘记了第17天是个休息日

1.654. 最大二叉树

题目链接:654. 最大二叉树
文档讲解: 代码随想录

我自己写的代码,直接调用max函数找到最大值,然后进行切割递归。

class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        #终止条件:树为空
        if not nums:
            return None
        
        #找到最大值为根节点
        root_val = max(nums)
        root = TreeNode(root_val)

        #找到切割点
        separator_index = nums.index(root_val)

        #切割
        nums_left = nums[:separator_index]
        nums_right = nums[separator_index + 1:len(nums)]

        #递归
        root.left = self.constructMaximumBinaryTree(nums_left)
        root.right = self.constructMaximumBinaryTree(nums_right)

        return root

标答思路:终止条件,在数组中只有一个元素的时候构造一个新节点返回;单层逻辑,找到数组中最大值以及对应的下标,根据下标左区间构造左子树,需要判断最大值下标大于0,以确保左子树至少有一个值,同理,要判断最大值下标小于数组长度减一,以确保右子树至少有一个值。

class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if len(nums) == 1:
            return TreeNode(nums[0])
        node = TreeNode(0)
        max_value = 0
        max_index = 0
        for i in range(len(nums)):
            if nums[i] > max_value:
                max_value = nums[i]
                max_index = i
        node.val = max_value
        if max_index > 0:
            nums_left = nums[:max_index]
            node.left = self.constructMaximumBinaryTree(nums_left)
        if max_index < len(nums) - 1:
            nums_right = nums[max_index + 1:len(nums)]
            node.right = self.constructMaximumBinaryTree(nums_right)
        return node
class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        return self.traversal(nums, 0, len(nums))
    
    def traversal(self, nums, left, right):
        #使用下标
        if left >= right:
            return None
        max_index = left
        for i in range(left + 1, right):
            if nums[i] > nums[max_index]:
                max_index = i
        node = TreeNode(nums[max_index])
        node.left = self.traversal(nums, left, max_index)
        node.right = self.traversal(nums, max_index + 1, right)
        return node

2.617.合并二叉树

题目链接:654. 最大二叉树
文档讲解: 代码随想录

class Solution(object):
    def mergeTrees(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: TreeNode
        """
        if not root1:
            return root2
        if not root2:
            return root1
        
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)

        return root1
class Solution(object):
    def mergeTrees(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: TreeNode
        """
        if not root1:
            return root2
        if not root2:
            return root1
        #新建一个node
        node = TreeNode(0)
        node.val = root1.val + root2.val 
        node.left = self.mergeTrees(root1.left,root2.left)
        node.right = self.mergeTrees(root1.right, root2.right)
        return node

迭代法:

class Solution(object):
    def mergeTrees(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: TreeNode
        """
        if not root1: 
            return root2
        if not root2: 
            return root1
        
        queue = collections.deque()
        queue.append(root1)
        queue.append(root2)

        while queue:
            node1 = queue.popleft()
            node2 = queue.popleft()

            if node1.left and node2.left: 
                queue.append(node1.left)
                queue.append(node2.left)
            if node1.right and node2.right: 
                queue.append(node1.right)
                queue.append(node2.right)
            
            node1.val += node2.val
            if not node1.left and node2.left:
                node1.left = node2.left
            if not node1.right and node2.right:
                node1.right = node2.right
            
        return root1
class Solution(object):
    def mergeTrees(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: TreeNode
        """
        if not root1:
            return root2
        if not root2:
            return root1
        
        queue = deque()
        queue.append((root1, root2))

        while queue:
            node1, node2 = queue.popleft()
            node1.val += node2.val

            if node1.left and node2.left:
                queue.append((node1.left, node2.left))
            elif not node1.left:
                node1.left = node2.left
            
            if node1.right and node2.right:
                queue.append((node1.right, node2.right))
            elif not node1.right:
                node1.right = node2.right
        return root1

3.700. 二叉搜索树中的搜索

题目链接:700. 二叉搜索树中的搜索
文档讲解: 代码随想录

class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        if not root or root.val == val:
            return root
        res = TreeNode(None)
        if val < root.val:
            res = self.searchBST(root.left, val)
        if val > root.val:
            res = self.searchBST(root.right, val)
        return res

迭代法:

class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        while root:
            if val < root.val:
                root = root.left
            elif val > root.val:
                root = root.right
            else:
                return root
        return None

使用栈遍历

class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        stack = [root]
        while stack:
            node = stack.pop()
            if node.val == val:
                return node
            if node.right:
                stack.append(node.right)
            if node.right:
                stack.append(node.left)
        return None

4.98.验证二叉搜索树

题目链接:98.验证二叉搜索树
文档讲解: 代码随想录

递归法,利用中序递增性质,转换成数组

class Solution(object):
    
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        vec = []
        self.traversal(root, vec)
        for i in range(1, len(vec)):
            if vec[i] <= vec[i -1]:
                return False
        return True

    def traversal(self, node, vec):
        #中序递归遍历
        if not node:
            return
        self.traversal(node.left, vec)
        vec.append(node.val)
        self.traversal(node.right, vec)

设定极小值,进行比较

class Solution(object):
    def __init__(self):
        self.max_val = float('-inf')
    
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        
        left = self.isValidBST(root.left)
        if self.max_val < root.val:
            self.max_val = root.val
        else:
            return False
        right = self.isValidBST(root.right)
        return left and right

这道题的两个陷阱:
(1)不能单纯的比较左节点小于中间节点,右节点大于中间节点。要比较的是左子树的所有节点都小于中间节点,右子树的所有节点都大于中间节点。
(2)建议避免初始化最小值,因此做出改进,取到最左面的节点数值来比较。

class Solution(object):
    def __init__(self):
        self.pre = None

    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        
        left = self.isValidBST(root.left)

        if self.pre and self.pre.val >= root.val:
            return False
        self.pre = root

        right = self.isValidBST(root.right)

        return left and right       

迭代法

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        #题目中说明树中节点数目大于等于1
        stack = []
        cur = root
        pre = None

        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                if pre and pre.val >= cur.val:
                    return False
                pre = cur
                cur = cur.right
        return True