终于刷完了，芜湖！🛫🛫🛫
这套题目集总体难度不高，适合刚学的时候作为随堂练习。
题目代码我也同步到GitHub仓库了🎈：https://github.com/Farmer-chong/LearnProcess/tree/master/Leetcode/leetcode-dataStruct-1

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

1
2
3
4
5
输入:
    2
   / \
  1   3
输出: true

示例 2:

1
2
3
4
5
6
7
8
9
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

解题思路&题解

因为是一颗二叉搜索树，因此每个节点都满足左边小、右边大这个特性。
因此每次判断的时候记录最小值和最大值，然后判断即可。解题思路如下：

  1. 由题目得知是整型，因此最大最小值分别为最小、最大的整型数值
  2. 当前节点值和最大最小值比较，错误则返回F
  3. 将当前节点的值作为最大、最小值传入左右子树
  4. 返回左右子树的判断结果
1
2
3
4
5
6
7
8
9
10
11
12
13
func isValidBST(root *TreeNode) bool {
	return validBST(root, math.MinInt64, math.MaxInt64)
}

func validBST(root *TreeNode, min, max int) bool {
	if root == nil {
		return true
	}
	if root.Val <= min || root.Val >= max {
		return false
	}
	return validBST(root.Left, min, root.Val) && validBST(root.Right, root.Val, max)
}

两数之和 IV - 输入 BST

给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

示例 1：

1
2
输入: root = [5,3,6,2,4,null,7], k = 9
输出: true

示例 2：

1
2
输入: root = [5,3,6,2,4,null,7], k = 28
输出: false

示例 3：

1
2
输入: root = [2,1,3], k = 4
输出: true

示例 4：

1
2
输入: root = [2,1,3], k = 1
输出: false

示例 5：

1
2
输入: root = [2,1,3], k = 3
输出: true

提示:

  • 二叉树的节点个数的范围是  [1, 104].
  • -104 <= Node.val <= 104
  • root 为二叉搜索树
  • -105 <= k <= 105

解题思路&题解

这题的解题思路大致和求两数和差不多，只是将for循环换成了递归遍历，然后利用hashMap存储已遍历的内容。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func findTarget(root *TreeNode, k int) bool {
	hashMap := make(map[int]bool, 100*100)
	return preOrder(root, hashMap, k)
}

func preOrder(root *TreeNode, hashMap map[int]bool, k int) bool {
	if root == nil {
		return false
	}
	if _, ok := hashMap[k-root.Val]; ok {
		return true
	}
	hashMap[root.Val] = true
	return preOrder(root.Left, hashMap, k) || preOrder(root.Right, hashMap, k)
}

二叉搜索树的最近公共祖先

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

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

例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

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

示例 2:

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

说明:

  • 所有节点的值都是唯一的。
  • p、q 为不同节点且均存在于给定的二叉搜索树中。

解题思路&题解

解题思路：

  1. 当前节点和p、q节点进行比较
  2. 如果是p、q节点、则返回该节点
  3. 获取左右子树的节点，当左右节点都存在，则证明当前节点为最近的祖先节点
  4. 如果只有单一一个节点，则继续将该节点返回
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	if root == p || root == q {
		return root
	}
	var leftNode, rightNode *TreeNode

	if p.Val > q.Val {
		// 左 大于 右 则交换。保证左边小于右边（p < q)
		p, q = q, p
	}
	leftNode = lowestCommonAncestor(root.Left, p, q)
	rightNode = lowestCommonAncestor(root.Right, p, q)
	if leftNode != nil && rightNode != nil {
		return root
	}
	if leftNode != nil {
		return leftNode
	}
	if rightNode != nil {
		return rightNode
	}
	return nil
}