绵阳梓潼网站制作公司

golang中怎么利用leetcode实现一个合法二叉搜索树

这篇文章将为大家详细讲解有关golang中怎么利用leetcode实现一个合法二叉搜索树，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。

10年积累的网站设计制作、成都网站设计经验，可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你，你也不认识我。但先网站制作后付款的网站建设流程，更有辰溪免费网站建设让你可以放心的选择与我们合作。

实现一个函数，检查一棵二叉树是否为二叉搜索树。

示例 1:

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

示例 2:

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

解题思路

1，如果没有叶子节点返回true

2，如果左子树非空，需要返回前缀节点路径上的最大值，且比根节点小

3，如果右子树非空，需要返回后缀节点路径上的最小值，且比根节点大

4，左右子树都是合法的

5，需要注意，不是前缀节点是前缀节点路径最大值

测试用例

[5,1,4,null,null,3,6]

[5,14,null,1]

代码实现

/** * Definition for a binary tree node. * type TreeNode struct { *     Val int *     Left *TreeNode *     Right *TreeNode * } */func isValidBST(root *TreeNode) bool {   if root==nil || (root.Left==nil && root.Right==nil) {       return true   }
   valid:=true   if root.Left!=nil{      l:=pre(root.Left)      if l>=root.Val{          valid=false      }      fmt.Println(l,root)   }   if root.Right!=nil{      r:=suc(root.Right)      if r<=root.Val{          valid=false      }       fmt.Println(r,root)   }   return valid && isValidBST(root.Left) && isValidBST(root.Right)}
func pre(root * TreeNode) int{    //root !=nil    max:=root.Val    cur:=root    for cur!=nil{        if cur.Right!=nil{            cur=cur.Right            if max            max=cur.Val            }        }else{            cur=cur.Left            if cur!=nil && max                max=cur.Val            }        }    }    return max}
func suc(root*TreeNode)int{     min:=root.Val    cur:=root    for cur!=nil{        if cur.Left!=nil{            cur=cur.Left            if min >cur.Val{            min=cur.Val            }        }else{            cur=cur.Right            if cur!=nil &&  min >cur.Val{                min=cur.Val            }        }    }    return min}

关于golang中怎么利用leetcode实现一个合法二叉搜索树就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。


分享题目：golang中怎么利用leetcode实现一个合法二叉搜索树
本文URL：http://myzitong.com/article/gspdhj.html

其他资讯