【二叉树系列】插入&删除&修剪&有序数组转二叉搜索树&二叉搜索树转换为累加树

//701. 二叉搜索树中的插入操作

//701. 二叉搜索树中的插入操作
func insertIntoBST(root *TreeNode, val int) *TreeNode {
	if root==nil{
		return &TreeNode{Val: val}
	}
	if root.Val<val{
		node:=insertIntoBST(root.Right,val)
		if  node.Val==val{
			root.Right=node
		}
	}
	if root.Val>val{
		node:=insertIntoBST(root.Left,val)
		if  node.Val==val{
			root.Left=node
		}
	}
	return root
}
//701. 二叉搜索树中的插入操作
func insertIntoBSTV1(root *TreeNode, val int) *TreeNode {
	if root==nil{
		return &TreeNode{Val: val}
	}
	cur:=root
	var temp *TreeNode
	for cur!=nil{
		if cur.Val<val{
			temp=cur
			cur=cur.Right
		}else{
			temp=cur
			cur=cur.Left
		}
	}
	if temp.Val<val{
		temp.Right= &TreeNode{Val: val}
	}else{
		temp.Left= &TreeNode{Val: val}
	}
	return root
}

//450. 删除二叉搜索树中的节点

/**
根据二叉搜索树的性质
	如果目标节点大于当前节点值，则去右子树中删除；
	如果目标节点小于当前节点值，则去左子树中删除；
	如果目标节点就是当前节点，分为以下三种情况：
		其无左子：其右子顶替其位置，删除了该节点；
		其无右子：其左子顶替其位置，删除了该节点；
		其左右子节点都有：其左子树转移到其右子树的最左节点的左子树上，然后右子树顶替其位置，由此删除了该节点。
出处详见：https://leetcode.cn/problems/delete-node-in-a-bst/solution/miao-dong-jiu-wan-shi-liao-by-terry2020-tc0o/
 */
func deleteNode(root *TreeNode,key int) *TreeNode {
	if root==nil{
		return root
	}
	cur:=root
	var pre *TreeNode
	for cur!=nil{
		if cur.Val==key{
			break
		}
		pre=cur
		if cur.Val<key{
			cur=cur.Right
		}else{
			cur=cur.Left
		}
	}
	if pre==nil{
		return deleteOneNode(cur)
	}
	if pre.Left!=nil && pre.Left.Val==key{
		fmt.Printf("Left %d\n",pre.Val)
		pre.Left=deleteOneNode(cur)
	}
	if pre.Right!=nil && pre.Right.Val==key{
		fmt.Printf("Right %d\n",pre.Val)
		pre.Right=deleteOneNode(cur)
	}
	return root
}
func deleteOneNode(target *TreeNode)*TreeNode{
	if target==nil{
		return target
	}
	if target.Right==nil{
		return target.Left
	}
	cur:=target.Right//找目标右节点的左叶子节点
	for cur.Left!=nil{
		fmt.Printf("cur %d\n",cur.Val)
		cur = cur.Left
	}
	cur.Left=target.Left//将目标的左节点全部赋值给上述中的左叶子节点
	return target.Right
}

//669. 修剪二叉搜索树

 
//669. 修剪二叉搜索树
func trimBST(root *TreeNode, low int, high int) *TreeNode {
	if root==nil{
		return nil
	}
	fmt.Printf("%d\n",root.Val)
	if root.Val<low{
		fmt.Printf("Right %d\n",root.Val)
		//low大于左的，则说明左侧必然也小于low，故使用右侧的树
		return trimBST(root.Right,low,high)
	}
	if root.Val>high{
		fmt.Printf("Left %d\n",root.Val)
		return trimBST(root.Left,low,high)
	}
	root.Left=trimBST(root.Left,low,high)
	root.Right=trimBST(root.Right,low,high)
	return root
}

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

 
//108. 将有序数组转换为二叉搜索树
func sortedArrayToBST(nums []int) *TreeNode {
	ln:=len(nums)
	if ln==0{
		return nil
	}
	index:=ln/2
	root:=TreeNode{
		nums[index],sortedArrayToBST(nums[:index]),
		sortedArrayToBST(nums[index+1:]),
	}
	return &root
}

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

 
//538. 把二叉搜索树转换为累加树
func convertBST(root *TreeNode) *TreeNode {
	var traceSum func(node *TreeNode)
	sum:=0//记录起始值
	traceSum= func(node *TreeNode) {
		if node==nil{
			return
		}
		traceSum(node.Right)
		fmt.Printf("%d \n",sum)
		sum+=node.Val
		node.Val=sum
		traceSum(node.Left)
	}
	traceSum(root)
	return root
}