今日任务：
资料来源：
题目
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3] 输出：1
示例 2：
输入：root = [1,0,48,null,null,12,49] 输出：1
提示：
注意：本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同
一开始想的是层序，因为一开始觉得这个最小绝对差一定出在父子节点之间。后来提交发现不对，二叉搜索树是有可能根节点和左子树的最右叶子的差值是最小的，只能中序。搜索二叉树只有中序出来的是有序数组。
python# 迭代写法
from collections import deque
from typing import Optional
# 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 getMinimumDifference(self, root: Optional[TreeNode]) -> int:
# 根据题目条件 必定有差值
queue = deque()
pointer1, pointer2 = root, TreeNode(val=0) # pointer2找个最小的 不能指向根节点 自己减自己就到0了 没法再比了
queue.append(pointer1)
result = 100000
while len(queue) != 0:
pointer1 = queue.pop()
if pointer1 is None:
pointer1 = queue.pop()
if abs(pointer2.val - pointer1.val) < result:
result = abs(pointer2.val - pointer1.val)
pointer2 = pointer1
else:
if pointer1.left is not None:
queue.append(pointer1.left)
queue.append(pointer1)
queue.append(None)
if pointer1.right is not None:
queue.append(pointer1.right)
return result
python# 递归写法
from typing import Optional
# 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.result = 100000
self.previous_root = TreeNode(val=0)
def minDiffInBST(self, root: Optional[TreeNode]) -> int:
self.recursion(root)
return self.result
def recursion(self, root: TreeNode):
if root is None:
return
self.recursion(root.right)
self.result = min(abs(self.previous_root.val - root.val), self.result)
self.previous_root = root
self.recursion(root.left)
题目
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
结点左子树中所含节点的值 小于等于 当前节点的值 结点右子树中所含节点的值 大于等于 当前节点的值 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2] 输出：[2]
示例 2：
输入：root = [0] 输出：[0]
提示：
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
这题学到了很重要的一点，只要是在中序遍历中，对二叉搜索树的操作都可以被视作对一个有序数组的操作。另外，这题对树遍历一次即可，遍历的同时对最大频率和当前频率同时进行更新。如果当前频率大于最大频率，那么更新最大频率并且清空结果数组再将当前的元素添加进去即可。
pythonfrom collections import deque
from typing import Optional, List
# 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.result = []
# self.previous_node = TreeNode(val=None)
def findMode(self, root: Optional[TreeNode]) -> List[int]:
stack = deque()
node = root
stack.append(node)
result = []
previous_val = None
count = 0
max_count = 1
while len(stack) != 0:
node = stack.pop()
if node is None:
node = stack.pop()
if previous_val is None: # 第一次进入比较 初始化
count = 1
previous_val = node.val
else:
if previous_val == node.val: # 相同
count += 1
else: # 不同 重新初始化
previous_val = node.val
count = 1
if count == max_count: #如果频率达到最大频率就添加元素
result.append(node.val)
elif count > max_count: # 如果当前元素超过最大频率 就清空数组 更新最大频率 再将当前元素添加进去
max_count = count
result.clear()
result.append(node.val)
else:
if node.left is not None:
stack.append(node.left)
stack.append(node)
stack.append(None)
if node.right is not None:
stack.append(node.right)
return result
题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 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
提示：
这道题一开始是自己写出来的，但是看过视频讲解之后才意识到，即使自己能想到大体的解法，看过视频还是有收获。
一开始的想法就是回溯，在后序遍历中，如果遇到要查找的节点（题目已经规定这个节点一定存在且值不相同），就回溯一个True。在一次递归中，同时收到的三个bool值：左子树回溯的值，右子树回溯的值，还有这次递归的根节点是否是要查找的节点。如果这三个值中有两个为True，就认为该节点是题目要求的“最近公共祖先”，修改类成员；如果只有一个为True，那么就直接返回True，表示以本次递归节点为根节点的子树中有要查找的节点；如果没有True，就返回False。为了加速，可以每次都检查类成员是否被赋值，如果是则直接跳过。
这题没有迭代解法，我认为原因在于迭代不能很好的保存具体的二叉树的层信息和左右位置信息，而递归栈可以保存下来。如果要使用迭代的话，会非常麻烦。
python# 我的代码
from collections import deque
# 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):
self.result = None
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
self.recursion(root, p, q)
return self.result
def recursion(self, root: TreeNode, p: TreeNode, q: TreeNode) -> bool:
if self.result is not None:
return True
if root is None:
return False
left = self.recursion(root.left, p, q)
right = self.recursion(root.right, p, q)
if p.val == root.val or q.val == root.val:
middle = True
else:
middle = False
if [left, right, middle].count(True) == 2 and self.result is None:
self.result = root
if True in (middle, left, right):
return True
return False
实际的解法是直接返回节点。在递归的的过程中，如果当前节点为空，则返回空；如果当前节点就是要找的节点，则直接返回该节点；再向左子树和右子树递归，如果递归回来的结果有一个不为空，则返回这个不为空的结果；如果两个都不为空，则返回这次递归的节点；如果两个都为空，则返回空。
这种解法极大地简化了逻辑判断，并且同时涵盖了要找的两个节点在同一节点下和不在同一节点下的两个情况。
pythonfrom typing import Optional
# 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':
return self.recursion(root, p, q)
def recursion(self, root: TreeNode, p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
if root is None:
return None
if root == p or root is q:
return root
left = self.recursion(root.left, p, q)
right = self.recursion(root.right, p, q)
if right is not None and left is not None:
return root
elif right is None and left is not None:
return left
elif right is not None and left is None:
return right
else:
return None
本文作者:御坂19327号
本文链接:
版权声明:本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！