530 二叉搜索树的最小绝对差 Easy
思路
这道题我们需要使用到二叉搜索树（BST）的一个特性：在二叉搜索树中，任意一个节点其左子树所有节点的值都小于该节点的值，其右子树所有节点的值都大于该结点的值。利用这个特性可以使得中序遍历按照从小到大的顺序访问树中所有的节点。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
def dfs(node):
if not node:
return
dfs(node.left)
self.res = min(self.res, node.val - self.pre)
self.pre = node.val
dfs(node.right)
self.res = float('inf')
self.pre = float('-inf')
dfs(root)
return self.res
|
时间复杂度
时间复杂度O(n)，空间复杂度O(n)，执行时间48ms，消耗内存18.4MB
230 二叉搜索树中第K小的元素 Medium
思路
和前一题一样，直接利用BST的特性去做，这题会更直观的展示BST的特性的用法。
这题我自己写的和我看到的解法我都写在下面，本质上都是一样的。
代码
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
stack = []
while True:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if not k:
return root.val
root = root.right
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
def dfs(node):
if not node or self.k == 0:
return
dfs(node.left)
self.k -= 1
if self.k == 0:
self.ans = node.val
return
dfs(node.right)
self.k = k
dfs(root)
return self.ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
def dfs(root):
if not root: return
dfs(root.left)
if self.k == 0: return
self.k -= 1
if self.k == 0: self.res = root.val
dfs(root.right)
self.k = k
dfs(root)
return self.res
|
时间复杂度
时间复杂度O(n)，空间复杂度O(n)，执行时间52ms，消耗内存19.8MB
时间复杂度O(n)，空间复杂度O(n)，执行时间67ms，消耗内存19.8MB
时间复杂度O(n)，空间复杂度O(n)，执行时间44ms，消耗内存19.8MB
98 验证二叉搜索树 Medium
思路
这道题需要引入两个边界，用于检验当前节点是否满足二叉搜索树的定义，其余和前面的思路一样
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def dfs(node, l = float('-inf'), r = float('inf')) -> bool:
if not node:
return True
pre = node.val
if pre <= l or pre >= r:
return False
if not dfs(node.left, l, pre):
return False
if not dfs(node.right, pre, r):
return False
return True
return dfs(root)
|
时间复杂度
时间复杂度O(n)，空间复杂度O(n)，执行时间44ms，消耗内存18.5MB
总结
这几道题都涉及到了二叉搜索树的特性，利用BST的特性可以更好的解决问题。
所以和前一篇一样，我们针对这类题型也总结了模板
中序遍历，适用于解决第k小，最小差值的问题
1
2
3
4
5
6
| def dfs(node):
if not node:
return
dfs(node.left)
dfs(node.right)
|
递归，适用于判断是否为BST
1
2
3
4
5
6
| def dfs(node, l, r):
if not node:
return True
if node.val <= l or node.val >= r:
return False
return dfs(node.left, l, node.val) and dfs(node.right, node.val, r)
|
栈，用于通过栈模拟中序遍历
1
2
3
4
5
6
7
8
9
10
11
| def kthSmallest(root, k):
stack = []
while True:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if not k:
return root.val
root = root.right
|
不管怎么变，实际上都需要借助二叉搜索树的特性，借助特性就可以直接解决问题了。