第十三天了！快刷完了~！😊🛫
题目开始涉及二叉树、二叉堆等难一点的操作了，还有二叉树的调整。
做完感觉知识点掌握的更扎实了，果然温故而知新啊！

二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

例如，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
给定二叉搜索树:

        4
       / \
      2   7
     / \
    1   3

和值: 2
你应该返回如下子树:

      2     
     / \   
    1   3

在上述示例中，如果要找的值是5，但因为没有节点值为 5，我们应该返回 NULL.

解题思路&题解

因为这是一颗搜索树，因此搜索功能实现起来特别简单，思路如下：

  1. 判断当前节点的值，相同则返回
  2. 判断当前节点的值与目标的值，根据大小选择左子树还是右子树
1
2
3
4
5
6
7
8
9
10
11
12
func searchBST(root *TreeNode, val int) *TreeNode {
	if root == nil || root.Val == val {
		return root
	}
	if root.Val > val {
		return searchBST(root.Left, val)
	}
	if root.Val < val {
		return searchBST(root.Right, val)
	}
	return nil
}

二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。

示例 1：

1
2
3
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：

示例 2：

1
2
输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

1
2
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

提示：

  • 给定的树上的节点数介于 0 和 10^4 之间
  • 每个节点都有一个唯一整数值，取值范围从 0 到 10^8
  • -10^8 <= val <= 10^8
  • 新值和原始二叉搜索树中的任意节点值都不同

解题思路&题解

这题感觉有点漏洞，因为这题是往一颗搜索二叉树里面插入一个数据，因此不会造成二叉树层数超标。
故思路如下：

  1. 用搜索的思路，查找出插入位置
  2. 往目标位置插入
1
2
3
4
5
6
7
8
9
10
11
func insertIntoBST(root *TreeNode, val int) *TreeNode {
	if root == nil {
		return &TreeNode{Val: val}
	}
	if root.Val < val {
		root.Right = insertIntoBST(root.Right, val)
	} else {
		root.Left = insertIntoBST(root.Left, val)
	}
	return root
}