跟随carl代码随想录刷题
语言：python

知识点介绍

• 🙋平衡二叉搜索数是不是二叉搜索树和平衡二叉树的结合？

• 💁是的，是二叉搜索树和平衡二叉树的结合。

• 🙋平衡二叉树与完全二叉树的区别在于底层节点的位置？

• 💁是的，完全二叉树底层必须是从左到右连续的，且次底层是满的。

• 🙋堆是完全二叉树和排序的结合，而不是平衡二叉搜索树？

• 💁堆是一棵完全二叉树，同时保证父子节点的顺序关系（有序）。 但完全二叉树一定是平衡二叉树，===>堆是平衡二叉树。

  • 堆的排序是父节点大于子节点，而搜索树是父节点大于左孩子，小于右孩子，所以堆不是平衡二叉搜索树。

700. 二叉搜索树中的搜索

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

题目分析

二叉搜索树是有序树，有如下特点：

• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉搜索树

搜索到目标节点要立即return

完整代码如下

递归法

# 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]:

        # 1. 输入类型：根节点，整数值；输出类型：子树节点或None
        # 2. 递归终止条件
        if not root or root.val == val:
            return root
        
        # 3. 单层循环逻辑
        if root.val < val:
            return self.searchBST(root.right, val)  # 因为搜索到目标节点了，所以要立即return
        if root.val > val:
            return self.searchBST(root.left, val)
        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]:

        while root:
            if root.val>val:
                root = root.left
            elif root.val<val:
                root = root.right
            else:
                return root
        return None

98. 验证二叉搜索树

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

题目分析

本题关键思路：中序遍历下，输出的二叉搜索树节点的数值是有序数列。

1. 先按递归法得出result数组，
2. 然后判断result是否为递增数组。

⭐️注意：result数组的值只能单调递增，不能有相等的情况。所以，出现result[i] >= result[i+1]都是return False。
如果根节点为空，也是二叉搜索树，返回True

💚二叉搜索树和中序遍历是好朋友！
💚二叉搜索树和中序遍历是好朋友！
💚二叉搜索树和中序遍历是好朋友！

陷阱：不能单纯中比较左节点小于中间节点，右节点小于中间节点，然后就返回True。这是不可以的！我们应该比较左节点以及它的所有子节点都小于中节点，右节点以及它的所有子节点都大于中节点。错误情况如图：

完整代码如下

递归法——中序遍历

# 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:
        # 1. 定义一个列表，用于存放结果集
        result = []

        # 2.1 定义中序遍历的函数
        def traversal(root):
            # 2.2 终止条件
            if not root:
                return 
            # 2.3 定义单层遍历函数
            traversal(root.left)
            result.append(root.val)
            traversal(root.right)
        # 3. 实例化函数
        traversal(root)

        # 4. 查看是否有序
        for i in range(len(result)-1):
            if result[i] >= result[i+1]:  # 注意：这里是`>=`
                return False
        
        # 5. 返回
        return True

迭代遍历——中序遍历

# 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:
        result = []
        st = []
        
        if root:
            st.append(root)

        while st:
            cur = st.pop()
            if cur:
                if cur.right:
                    st.append(cur.right)
                st.append(cur)
                st.append(None)
                if cur.left:
                    st.append(cur.left)
            else:
                cur = st.pop()
                result.append(cur.val)
        for i in range(len(result)-1):
            if result[i]>=result[i+1]:
                return False
        return True