代码随想录-Day20_代码随想录 day20

# lc654 最大二叉树
#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 
        node_val=max(nums)
        root=TreeNode(node_val)
        node_idx=nums.index(node_val)
        node_left=nums[:node_idx]
        node_right=nums[node_idx+1:]
        root.left=self.constructMaximumBinaryTree(node_left)
        root.right=self.constructMaximumBinaryTree(node_right)
        return root
        

#lc617 合并二叉树
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        #【二轮】掌握迭代法
        if not root1 and not root2:
            return
        if not root1:  return root2####【二轮】看一遍，这是答案代码，我的代码是： if not root1: root1=TreeNode(0)
        if not root2:  return root1####【二轮】看一遍，这是答案代码，我的代码是： if not root2: root2=TreeNode(0)
        root=TreeNode(root1.val+root2.val)
        root.left=self.mergeTrees(root1.left, root2.left)
        root.right=self.mergeTrees(root1.right, root2.right)
        return root

#700 二叉搜索树中的搜索
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:#迭代法
        #二叉搜索树是一个有序树：(左小右大)
        # 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
        # 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
        # 它的左、右子树也分别为二叉搜索树
       # if not root:
       #     return
        while root:
            #print(root)
            if root.val==val:
                return root
            elif root.val>val:
                root=root.left####此处是root.left 而非root.right
            elif root.val<val:####反之亦然
                root=root.right
        return
 

#lc98 验证二叉搜索树
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        #递归+数组升序判断解法，此方法较繁琐【二轮】学会迭代+双指针解法
        result=[]
        if not root:
            return False
        def Traversal(node):
            if not node:
                return
            Traversal(node.left)
            result.append(node.val)
            Traversal(node.right)
        Traversal(root)
        for i in range(len(result)-1):
            if result[i]>=result[i+1]:
                return False
        return True
 
 
迭代-中序遍历
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        stack = []
        cur = root
        pre = None
        while cur or stack:
            if cur: # 指针来访问节点，访问到最底层
                stack.append(cur)
                cur = cur.left
            else: # 逐一处理节点
                cur = stack.pop()
                if pre and cur.val <= pre.val: # 比较当前节点和前节点的值的大小
                    return False
                pre = cur 
                cur = cur.right
        return True
 
# 遵循Carl的写法，只添加了节点判断的部分
class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        # method 2
        que, pre = [], None
        while root or que:
            while root:
                que.append(root)
                root = root.left
            root = que.pop()
            # 对第一个节点只做记录，对后面的节点进行比较
            if pre is None:
                pre = root.val
            else:
                if pre >= root.val: return False
                pre = root.val
            root = root.right
        return True