网站制作 网站建设怎么做的,网站部署到终端机怎么做,厦门网站营销,奢侈品网站模板type TreeNode struct { Val int Left *TreeNode Right *TreeNode
}
//669. 修剪二叉搜索树
//本题与450. 删除二叉搜索树中的节点 相似#xff0c;不同之处在于本题删除不止一个节点#xff0c;450不需要遍历全部二叉树#xff0c;但本题需要全部遍历#xff0c;而且…type TreeNode struct { Val int Left *TreeNode Right *TreeNode
}
//669. 修剪二叉搜索树
//本题与450. 删除二叉搜索树中的节点 相似不同之处在于本题删除不止一个节点450不需要遍历全部二叉树但本题需要全部遍历而且要随时调整二叉树结构
func trimBST(root *TreeNode, low int, high int) *TreeNode { if root nil { return root } //找到要删除的左子树 if root.Val low { //因为不确定左子树是否还要删除因此要不断向右遍历因为是二叉树搜索树当前节点如果比low小当前节点左子树一定比low小因此直接舍弃不用遍历 right : trimBST(root.Right, low, high) return right } if root.Val high { //同样因为不确定右子树是否还要删除因此要不断向左遍历因为是二叉树搜索树当前节点如果比high 大当前节点右子树一定比high 大因此直接舍弃不用遍历 life : trimBST(root.Left, low, high) return life } root.Left trimBST(root.Left, low, high) root.Right trimBST(root.Right, low, high) return root } //108. 将有序数组转换为二叉搜索树
//因为是有序数组让中间节点作为根据节点然后进行前序遍历中左右
func sortedArrayToBST(nums []int) *TreeNode { if len(nums) 0 { return nil }
//寻找中间值索引 mid : len(nums) / 2 root : TreeNode{Val: nums[mid]} //中 root.Left sortedArrayToBST(nums[:mid]) //左 root.Right sortedArrayToBST(nums[mid1:]) //右 return root }
//538. 把二叉搜索树转换为累加树 func convertBST(root *TreeNode) *TreeNode { if root nil { return nil } prev : 0 var traversal func(tree *TreeNode) traversal func(tree *TreeNode) { if tree nil { return } // 中序遍历是左中右但我们要先取最大值所以要逆中序遍历即右中左 traversal(tree.Right) // 右 tree.Val tree.Val prev //中 prev tree.Val //把当前值传给前一个指针 traversal(tree.Left) //左 } traversal(root) return root }
