Day 18 卡玛笔记

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

递归法

# 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 __init__(self):
        self.pre=None
        self.res=float('inf')
    def traversal(self,cur):
        # 递归终止条件
        if cur==None:
            return

        # 递归逻辑
        self.traversal(cur.left)    # 左
        # 第一次时遍历到最左边的节点，将pre指针指向cur指针
        if self.pre==None:
            self.pre=cur
        else:
            self.res=min(self.res,cur.val-self.pre.val)
            self.pre=cur
        self.traversal(cur.right)   # 右
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        self.traversal(root)
        return self.res

运行结果

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值
• 左子树和右子树都是二叉搜索树

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

双指针法

# 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 __init__(self):
        # 结果集
        self.res=[]
        # 前一个指针
        self.pre=None
        # 计算单个元素频率
        self.count=1
        # 计算最大频率
        self.max_count=1
    def traversal(self,cur):
        # 递归终止条件
        if cur==None:
            return
        
        # 递归逻辑
        self.traversal(cur.left)    # 前
        # 遍历到最左边，这次递归先把pre指针指向cur
        if self.pre==None:
            self.pre=cur
        else:
            # 如果两指针元素相同
            if self.pre.val==cur.val:
                self.count+=1
            # 两指针元素不同，开始收割结果
            else:
                # 如果当前元素频率等于最大频率，则将对应元素存入结果值
                if self.count==self.max_count:
                    self.res.append(self.pre.val)
                    
                # 如果当前元素频率大于最大频率，则更新最大频率值，且将res数组更新
                elif self.count>self.max_count:
                    self.max_count=self.count
                    self.res=[self.pre.val]
                # 重置计数
                self.count=1
            # 更新pre指针
        self.pre=cur
        self.traversal(cur.right)   # 右
        
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        self.traversal(root)
        # 处理最后一个节点的频率
        if self.count==self.max_count:
            self.res.append(self.pre.val)
        elif self.count>self.max_count:
            self.res=[self.pre.val]
        return self.res

运行结果

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 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 lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 递归终止条件
        if root==q or root==p or root==None:
            return root
        
        # 递归逻辑
        left=self.lowestCommonAncestor(root.left,p,q)    # 左
        right=self.lowestCommonAncestor(root.right,p,q)   # 右
        # 如果左右子树都找到
        if left!=None and right!=None:
            return root
        # 如果只找到左子树
        if left!=None and right==None:
            return left
        # 如果只找到右子树
        if left==None and right!=None:
            return right
        # 如果都没找到
        if left==None and right==None:
            return None

运行结果

有问题欢迎评论或私信