501. 二叉搜索树中的众数

一、501. 二叉搜索树中的众数 1.1、题目描述

1.2、题解 1.2.1、中序遍历 结果升序

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self) -> None:
        self.pre = -1
        self.count = 0
        # target[0] 记录最大的记录数， target[1:] 记录众数元素
        self.target = [0, 0]
        
    def findMode(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        
        self.inorderTraversal(root) 
        
        print(self.target, self.pre, self.count)
        
        # 最后的数没有对比，
        if self.count > self.target[0]:
            self.target = [self.count, self.pre]
        elif self.count == self.target[0]:
            self.target.append(self.pre)
        return self.target[1:]
            
        
        
    
    # 中序遍历: 先遍历左子树， 再遍历根节点， 最后遍历右子树
    def inorderTraversal(self, root: TreeNode) -> None:
        if not root:
            return None
        # 左子树
        if root.left:
            self.inorderTraversal(root.left)
        
        # 根节点
        if self.pre == -1:
            self.pre = root.val
            self.count = 1
        elif self.pre == root.val:
            self.count += 1
        else:
        	
            if self.count > self.target[0]:
            	# 更新众数
                self.target  = [self.count, self.pre]
            elif self.count == self.target[0]:
            	# 众数有多个, 追加众数
                self.target.append(self.pre)
            self.pre = root.val
            self.count = 1
        
        
        # 右子树
        if root.right:
            self.inorderTraversal(root.right)
        

二、530. 二叉搜索树的最小绝对差

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self) -> None:
        self.min = float('inf')
        self.pre = -1
    def getMinimumDifference(self, root: TreeNode) -> int:
        self.inorderTraversal(root)
        return self.min
        
    # 中序遍历: 先遍历左子树， 再遍历根节点， 最后遍历右子树
    def inorderTraversal(self, root: TreeNode) -> None:
        # 左子树
        if root.left:
            self.inorderTraversal(root.left)
        
        # 根节点
        if self.pre != -1:
            self.min = min(self.min, abs(self.pre - root.val))
        self.pre = root.val
        
        
        # 右子树
        if root.right:
            self.inorderTraversal(root.right)