golang刷leetcode 二叉树（1）验证二叉搜索树

golangLeetcode

发布于 2022-08-02 15:57:31

1960

发布于 2022-08-02 15:57:31

文章被收录于专栏：golang算法架构leetcode技术php

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1:

输入:
    2
   / \
  1   3
输出: true

示例 2:

输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

解题思路：

1，中序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
var last=^(int(^uint(0) >> 1))
func isValidBST(root *TreeNode) bool {
    if root!=nil{
        if!isValidBST(root.Left){
            return false
        }
        if last>=root.Val{
            return false
        }
        last=root.Val
        if !isValidBST(root.Right){
            return false
        }
    }
    return true
}

方法二：

递归：根节点>大于左节点最大值，小于右节点最小值

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    if root==nil{
        return true
    }
    if root.Left!=nil&& root.Right!=nil{
        l:=maxBST(root.Left)
        r:=minBST(root.Right)
        return isValidBST(root.Left)&&isValidBST(root.Right)&&l<root.Val && root.Val<r
    }
    if root.Left!=nil{
         l:=maxBST(root.Left)
        return isValidBST(root.Left)&&l<root.Val
    }
    if root.Right!=nil{
         r:=minBST(root.Right)
        return isValidBST(root.Right)&&root.Val<r
    }
    return true
}

func maxBST(root *TreeNode)int{
    if root.Right!=nil{
        return maxBST(root.Right)
    }
    return root.Val
}

func minBST(root *TreeNode)int{
    if root.Left!=nil{
        return minBST(root.Left)
    }
    return root.Val
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-03-30，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树