代码随想录算法训练营第二十二天 669.修建二叉搜索树、108.将有序数组转化为二叉搜索树、538.把二叉搜索树转化为累加树

669.修建二叉搜索树

题目链接：力扣题目链接

文章讲解：代码随想录(https://programmercarl.com)

视频讲解：你修剪的方式不对，我来给你纠正一下！| LeetCode：669. 修剪二叉搜索树

状态：AC

思路

与昨天最后一道题类似，昨天最后一道题要求删除一个节点，这道题则为批量删除节点，多加一个判断条件即可

链接跳转

先使用前序遍历得到树的所有节点，再以此判断改节点是否应该删除

代码

func trimBST(root *TreeNode, low int, high int) *TreeNode {
	path := []int{}
	pre(root, &path)
	for _, v := range path {
		if !(low <= v && v <= high) {
			root = deleteNode(root, v)
		}
	}
	return root
}

func pre(root *TreeNode, path *[]int) {
	if root == nil {
		return
	}
	*path = append(*path, root.Val)
	pre(root.Left, path)
	pre(root.Right, path)
}

108.将有序数组转化为二叉搜索树

题目链接：力扣题目链接

文章讲解：代码随想录(https://programmercarl.com)

视频讲解：构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树

状态：AC

思路

根据二叉搜索树的定义，比根节点小的值在根节点左侧，比根节点大的值在根节点右侧。而且还要建立平衡搜索树，那么根节点应该为数组最中间的那个值。切割数组，然后递归

代码

func sortedArrayToBST(nums []int) *TreeNode {
	if len(nums) == 0 {
		return nil
	}
	root := backTracking(nums, 0, len(nums)-1)
	return root
}

func backTracking(nums []int, left, right int) *TreeNode {
	if left > right {
		return nil
	}
	mid := (left + right) / 2
	root := &TreeNode{
		Val:   nums[mid],
		Left:  backTracking(nums, left, mid-1),
		Right: backTracking(nums, mid+1, right),
	}
	return root
}

538.把二叉搜索树转化为累加树

题目链接：力扣题目链接

文章讲解：代码随想录(https://programmercarl.com)

视频讲解：普大喜奔！二叉树章节已全部更完啦！| LeetCode：538.把二叉搜索树转换为累加树

状态：AC

思路

看到树的构建过程，实际上是对树进行“右根左”的遍历。使用双指针，一个指向当前节点，另一个指向过去的节点。当前结点的新的值要加上过去节点的值。总体思路与530题思路一样。跳转链接

代码

func convertBST(root *TreeNode) *TreeNode {
	var pre *TreeNode
	var function func(cur *TreeNode)
	function = func(cur *TreeNode) {
		if cur == nil {
			return
		}
		function(cur.Right)
		if pre != nil {
			cur.Val += pre.Val
		}
		pre = cur
		function(cur.Left)
	}
	function(root)
	return root
}