当前位置 : 主页 > 编程语言 > 其它开发 >

98. 验证二叉搜索树 前序遍历解法以及后续遍历解法(go语言)

来源:互联网 收集:自由互联 发布时间:2022-05-30
leetcode题目 98. 验证二叉搜索树 前序遍历 最简洁的答案版本,由于先判断的是根节点,所以直接判断当前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的根,我们对他做判断,然后把结果向上传递,得到答案

上一篇:实验四
下一篇:没有了
网友评论