[二叉搜索树] 🌲 BST

[Linjiayu6]

0 - 概念

左边子树值 < root.val
右边子树值 > root.val

通过使用【中序遍历】 left => root => right 路径判断 是否是递增的序列

[Linjiayu6]

1 - 剑指 Offer 33. 二叉搜索树的后序遍历序列

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        _len = len(postorder)
        if _len == 0 or _len == 1 or _len == 2: return True

        root_val = postorder.pop(-1)
        i = 0
        while i < len(postorder):
            if postorder[i] > root_val: break
            i += 1

        left = postorder[0: i]
        right = postorder[i: ]
        # 判断right所有值是否均大于 root_val
        for r in right:
            if r < root_val: return False
        
        r = self.verifyPostorder(left)
        l = self.verifyPostorder(right)
        if r == False or l == False: return False
        return True

[Linjiayu6]

2 - 230. 二叉搜索树中第K小的元素 中序遍历

同 剑指 Offer 54. 二叉搜索树的第k大节点

都是 深度优先遍历, 可以去看看树🌲的前中后序遍历

# 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 kthSmallest(self, root: TreeNode, k: int) -> int:
        # 中序遍历 left, root, right
        if root is None: return None
        stack = [(root, 'light')]
        i = 1
        while stack:
            (node, flag) = stack.pop()
            if node:
                if flag == 'light':
                    if node.right: stack.append((node.right, 'light'))
                    stack.append((node, 'grey'))
                    if node.left: stack.append((node.left, 'light'))
                else:
                    if i == k: return node.val
                    else: i+= 1

2 - 剑指 Offer 36. 二叉搜索树与双向链表 中序遍历

同 426. 将二叉搜索树转化为排序的双向链表

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""
class Solution(object):
    def treeToDoublyList(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if root is None: return None
        # 中序遍历 左 中 右
        stack = [(root, 'light')]
        head = Node(None) # 指针
        
        prevtmp = head
        while stack:
            (node, key) = stack.pop()
            if node:
                if key == 'light':
                    if node.right: stack.append((node.right, 'light'))
                    stack.append((node, 'grey'))
                    if node.left: stack.append((node.left, 'light'))
                else:
                    prevtmp.right = node # 指向后面的节点
                    node.left = prevtmp
                    prevtmp = node
        _minNode = head.right

        _minNode.left = prevtmp
        prevtmp.right = _minNode
        return head.right