建设网站网站建设公司,营销型网站公司名称,网站推广工具有,wordpress rockgroup前言
写完这三道题#xff0c;二叉树部分就先告一段落了。其实还有很多模糊的地方。
内容
一、修剪二叉搜索树
669. 修剪二叉搜索树
给你二叉搜索树的根节点 root #xff0c;同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树#xff0c;使得所有节点的值在[l…前言
写完这三道题二叉树部分就先告一段落了。其实还有很多模糊的地方。
内容
一、修剪二叉搜索树
669. 修剪二叉搜索树
给你二叉搜索树的根节点 root 同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即如果没有被移除原有的父代子代关系都应当保留)。 可以证明存在 唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意根节点可能会根据给定的边界发生改变。
递归
func trimBST(root *TreeNode, low int, high int) *TreeNode {if rootnil{return root}if root.Vallow{return trimBST(root.Right,low,high)}if root.Valhigh{return trimBST(root.Left,low,high)}root.LefttrimBST(root.Left,low,high)root.RighttrimBST(root.Right,low,high)return root
}
迭代
func trimBST(root *TreeNode,low,high int)*TreeNode{// 处理 root让 root 移动到[low, high] 范围内注意是左闭右闭for root!nil(root.Vallow||root.Valhigh){if root.Vallow{rootroot.Right}else{rootroot.Left}}if rootnil{return nil}//必须在这里先判断// 此时 root 已经在[low, high] 范围内处理左孩子元素小于 low 的情况左节点是一定小于 root.Val因此天然小于 highfor node:root; node.Left!nil;{if node.Left.Vallow{node.Leftnode.Left.Right}else{nodenode.Left}}// 此时 root 已经在[low, high] 范围内处理右孩子大于 high 的情况for node:root; node.Right!nil;{if node.Right.Valhigh{node.Rightnode.Right.Left}else{nodenode.Right}}return root
}
二、将有序数组转换为二叉搜索树
108. 将有序数组转换为二叉搜索树
给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
递归
func sortedArrayToBST(nums []int) *TreeNode {if len(nums)0{//终止条件return nil}mid:len(nums)/2root:TreeNode{Val:nums[mid],}root.LeftsortedArrayToBST(nums[:mid])root.RightsortedArrayToBST(nums[mid1:])return root
} 三、把二叉搜索树转换为累加树
538. 把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点该树的节点值各不相同请你将其转换为累加树Greater Sum Tree使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下二叉搜索树满足下列约束条件
节点的左子树仅包含键 小于 节点键的节点。节点的右子树仅包含键 大于 节点键的节点。左右子树也必须是二叉搜索树。
反序中序遍历
func convertBST(root *TreeNode) *TreeNode {sum:0var dfs func(*TreeNode)dfsfunc(node *TreeNode){if node!nil{dfs(node.Right)sumnode.Valnode.Valsumdfs(node.Left)}}dfs(root)return root
}
最后
写个总结吧。下一站回溯算法
