用dw制作学校网站教程,用dw做网站怎么添加水平线,信宜网站设计公司,wordpress 语言文件夹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 }
