如何用Go语言实现二叉搜索树的前序和后序遍历验证？
- 内容介绍
- 文章标签
- 相关推荐
本文共计781个文字，预计阅读时间需要4分钟。
LeetCode 题目+98. 验证二叉搜索树+前序遍历+最简洁的答案版本，由于先判断的是根节点的值v，所以直接判断当前root的值v是否大于左子树最大值且小于右子树最小值，然后递归遍历左右子树。
前序遍历leetcode题目 98. 验证二叉搜索树
最简洁的答案版本，由于先判断的是根节点，所以直接判断当前root的值v，是否满足大于左子树最大，小于右子树最小，然后再遍历左子树，右子树是否是这样
func isValidBST(root *TreeNode) bool {
return dfs(root,math.MinInt64,math.MaxInt64)
}
func dfs(root *TreeNode,min float64,max float64) bool {
if root == nil {
return true
}
v := float64(root.Val)
if v > min && v < max && dfs(root.Left,min,v) && dfs(root.Right,v,max) { // 'min'是右子树最小，因为'dfs(root.Right,v,max)'遍历时'max'保持不变，发生回溯后不断把较小v（因为v必须比右子树小）回溯，同理'max'是左子树最大
return true
}else {
return false
}
}
后续遍历
最开始我参考 110. 平衡二叉树 的做法，想进行后续遍历解法，一直失败，后来根据前序遍历的经验才得到结果
根据注释，可以清楚看到和前序的异曲同工之妙
func isValidBST(root *TreeNode) bool {
ok,_,_ := judge(root)
return ok
}
func judge(root *TreeNode) (bool,int,int){// 利用go的多返回值向上传递，与前序遍历到结束时回溯相反
if root == nil {
return true,math.MinInt64,math.MaxInt64
}
lok,lmax,lmin := judge(root.Left) // 得到左子树中最大最小的值以及是否符合搜索二叉
rok,rmax,rmin := judge(root.Right)// 得到右子树中最大最小的值以及是否符合搜索二叉
if lok == true && rok == true && root.Val > lmax && root.Val < rmin {
// 检查当前根是否大于左子树中最大值，小于右子树最小值
if lmin > root.Val {
lmin = root.Val
// 由于当前根的值是当前树中最小的（因为左子树最小值已经是最小的了）
}
if rmax < root.Val {
rmax = root.Val
// 由于当前根的值是当前树中最大的
}
return true,rmax,lmin //判断是一个搜索二叉树，返回当前最大，最小值
}else {
return false,0,0
}
}
如何破解此类需要递推的题
我提供一个思路：考虑最极端的情况。例如这道题中，
前序遍历，由于是根左右的顺序,我们的操作肯定是对根操作的(因为根是当前的实体),那么极端情况就是,最大的根,于是我们考虑了判断当前root的值v，是否满足大于左子树最大，小于右子树最小,然后再去遍历左右,直到结尾开始回溯,得到答案
后续遍历,由于是左右根的顺序,那么左右肯定在不断遍历,直到最结尾,我们找到了最后一个不是nil的根,我们对他做判断,然后把结果向上传递,得到答案
本文共计781个文字，预计阅读时间需要4分钟。
LeetCode 题目+98. 验证二叉搜索树+前序遍历+最简洁的答案版本，由于先判断的是根节点的值v，所以直接判断当前root的值v是否大于左子树最大值且小于右子树最小值，然后递归遍历左右子树。
前序遍历leetcode题目 98. 验证二叉搜索树
最简洁的答案版本，由于先判断的是根节点，所以直接判断当前root的值v，是否满足大于左子树最大，小于右子树最小，然后再遍历左子树，右子树是否是这样
func isValidBST(root *TreeNode) bool {
return dfs(root,math.MinInt64,math.MaxInt64)
}
func dfs(root *TreeNode,min float64,max float64) bool {
if root == nil {
return true
}
v := float64(root.Val)
if v > min && v < max && dfs(root.Left,min,v) && dfs(root.Right,v,max) { // 'min'是右子树最小，因为'dfs(root.Right,v,max)'遍历时'max'保持不变，发生回溯后不断把较小v（因为v必须比右子树小）回溯，同理'max'是左子树最大
return true
}else {
return false
}
}
后续遍历
最开始我参考 110. 平衡二叉树 的做法，想进行后续遍历解法，一直失败，后来根据前序遍历的经验才得到结果
根据注释，可以清楚看到和前序的异曲同工之妙
func isValidBST(root *TreeNode) bool {
ok,_,_ := judge(root)
return ok
}
func judge(root *TreeNode) (bool,int,int){// 利用go的多返回值向上传递，与前序遍历到结束时回溯相反
if root == nil {
return true,math.MinInt64,math.MaxInt64
}
lok,lmax,lmin := judge(root.Left) // 得到左子树中最大最小的值以及是否符合搜索二叉
rok,rmax,rmin := judge(root.Right)// 得到右子树中最大最小的值以及是否符合搜索二叉
if lok == true && rok == true && root.Val > lmax && root.Val < rmin {
// 检查当前根是否大于左子树中最大值，小于右子树最小值
if lmin > root.Val {
lmin = root.Val
// 由于当前根的值是当前树中最小的（因为左子树最小值已经是最小的了）
}
if rmax < root.Val {
rmax = root.Val
// 由于当前根的值是当前树中最大的
}
return true,rmax,lmin //判断是一个搜索二叉树，返回当前最大，最小值
}else {
return false,0,0
}
}
如何破解此类需要递推的题
我提供一个思路：考虑最极端的情况。例如这道题中，
前序遍历，由于是根左右的顺序,我们的操作肯定是对根操作的(因为根是当前的实体),那么极端情况就是,最大的根,于是我们考虑了判断当前root的值v，是否满足大于左子树最大，小于右子树最小,然后再去遍历左右,直到结尾开始回溯,得到答案
后续遍历,由于是左右根的顺序,那么左右肯定在不断遍历,直到最结尾,我们找到了最后一个不是nil的根,我们对他做判断,然后把结果向上传递,得到答案