最大二叉树

654. 最大二叉树

给定一个不含重复元素的整数数组 nums 。 你需要从 nums 中找出最大的数，将其作为二叉树的根节点，然后递归地构建左子树和右子树。
左子树的构建过程是从数组中 最大值左边 的 子数组中 构建出最大二叉树 。
右子树的构建过程是从数组中 最大值右边 的 子数组中 构建出最大二叉树 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        if len(nums) == 1:     #只有一个点就创建以这个为点的树
            return TreeNode(nums[0])
        node = TreeNode(0) #创建节点设置值为零
        max_n = 0
        index_n = 0
        for i in range(len(nums)):
            if nums[i] > max_n:
                max_n =nums[i]
                index_n = i
        node.val = max_n
        if index_n > 0:
            left_num = nums[0:index_n]
            node.left = self.constructMaximumBinaryTree(left_num)
        if index_n < len(nums)-1:
            right_num = nums[index_n+1:]
            node.right = self.constructMaximumBinaryTree(right_num)
        return node

递归法，递归三部曲：

  1. 确定递归函数的参数和返回值（nums）
  2. 确定递归的终止条件（数组长度为1）
  3. 确定单层递归的逻辑（找到最大值和索引，创建节点，递归左子树和右子树）

合并二叉树

617. 合并二叉树

给你两棵二叉树： root1 和 root2 。想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。

1
2
3
4
5
6
7
8
9
10
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

递归法，递归三部曲：

  1. 确定递归函数的参数和返回值（root1,root2）
  2. 确定递归的终止条件（root1为空返回root2，root2为空返回root1）(包含都为空的情况)
  3. 确定单层递归的逻辑（将root2的值加到root1上，递归左子树和右子树）

搜索二叉树

递归法

700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。你需要在 BST 中找到节点值等于 val 的节点。返回以该节点为根的子树。如果节点不存在，则返回 null 。

1
2
3
4
5
6
7
8
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root or root.val == val:
            return root
        if val < root.val:
            return self.searchBST(root.left,val)
        if val > root.val:
            return self.searchBST(root.right,val)

递归法，递归三部曲：

  1. 确定递归函数的参数和返回值（root,val）(注意题目要求的返回值是节点（值为val的节点）)
  2. 确定递归的终止条件（root为空返回None，root值等于val返回root）
  3. 确定单层递归的逻辑（如果val小于root值，递归左子树，否则递归右子树）

迭代法

1
2
3
4
5
6
7
8
9
10
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        while root:
            if val < root.val:
                root=root.left
            elif val > root.val:
                root = root.right
            else :
                return root
        return None

迭代法，循环遍历二叉搜索树，找到值为val的节点，返回该节点。如果遍历完整个树都没有找到，返回None。

验证二叉搜索树

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def __init__(self):
        self.pre = None
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        
        if root is None:
            return True
        left = self.isValidBST(root.left)
        if  self.pre is not None and self.pre.val >= root.val:
            return False
        self.pre = root
        right = self.isValidBST(root.right)
        return left and right

递归法，递归三部曲：

  1. 确定递归函数的参数和返回值（root）(注意题目要求的返回值是布尔值)
  2. 确定递归的终止条件（root为空返回True）
  3. 确定单层递归的逻辑（中序遍历，判断当前节点是否大于前一个节点，递归左子树和右子树）
    在这道题我遇到了个很有意思的错误，就是我把self.pre = None放在isValidBST里面，欸，产生了一直返回True的情况，按照以前ai教我的，把这个放在里面按道理是防止污染，是好的，我仔细思考了一下，因为在这道题pre是不可以被重新初始化的，放在isValidBST里面会导致每次递归都重新初始化pre，所以会一直返回True。所以再__init__里面创建一次最好