关于golang:golangleetcode初级验证二叉搜索树对称二叉树

第一题 验证二叉搜寻树

题目信息

解题思路

所有左子树和右子树本身必须也是二叉搜寻树。
显然这能够用递归的形式解决
咱们只需验证根节点的值大于所有左子树的值,小于所有右子树的值即可
即 将根节点别离与左子树的最大节点,根节点与右子树的最小节点比拟

代码如下

func isValidBST(root *TreeNode) bool {
     if root.Left==nil && root.Right==nil{
         return true
    }
    if root.Val<max(root.Left) {
        return false
    }else if root.Val>min(root){
        return  false
    }else{
        return isValidBST(root.Right)&&isValidBST(root.Left)
    }
}
func max(root *TreeNode) int {
    
}
func min(root *TreeNode) int {
    
}

max与min函数未实现
因为咱们并不能保障子树是规范的二叉搜寻树
想要在子树中找到最大与最小的值并不是件容易的事
遍历搜寻树显然更简单

故咱们须要扭转递归的函数

同时思考遍历子树的时候也给了咱们启发
树的三种遍历程序 先序遍历中序遍历后续遍历
别离是指遍历的时候树的根节点排在左右子树的后面,两头,前面
而按中序遍历的程序,二叉搜寻树失去的值的序列为升序序列
这就失去了更为简洁的解法

递归

代码

func isValidBST(root *TreeNode) bool {
    return helper(root, math.MinInt64, math.MaxInt64)
}

func helper(root *TreeNode, lower, upper int) bool {
    if root == nil {
        return true
    }
    if root.Val <= lower || root.Val >= upper {
        return false
    }
    return helper(root.Left, lower, root.Val) && helper(root.Right, root.Val, upper)
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/
起源:力扣(LeetCode)
著作权归作者所有。商业转载请分割作者取得受权,非商业转载请注明出处。

复杂度剖析

工夫复杂度 : O(n),其中 n 为二叉树的节点个数。在递归调用的时候二叉树的每个节点最多被拜访一次,因而工夫复杂度为 O(n)。

空间复杂度 : O(n),其中 n 为二叉树的节点个数。递归函数在递归过程中须要为每一层递归函数调配栈空间,所以这里须要额定的空间且该空间取决于递归的深度,即二叉树的高度。最坏状况下二叉树为一条链,树的高度为n ,递归最深达到 n 层,故最坏状况下空间复杂度为 O(n)

中序遍历

代码

func isValidBST(root *TreeNode) bool {
    stack := []*TreeNode{}
    inorder := math.MinInt64
    for len(stack) > 0 || root != nil {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        root = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if root.Val <= inorder {
            return false
        }
        inorder = root.Val
        root = root.Right
    }
    return true
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/validate-binary-search-tree/solution/yan-zheng-er-cha-sou-suo-shu-by-leetcode-solution/
起源:力扣(LeetCode)
著作权归作者所有。商业转载请分割作者取得受权,非商业转载请注明出处。

复杂度剖析

工夫复杂度 : O(n),其中 n 为二叉树的节点个数。二叉树的每个节点最多被拜访一次,因而工夫复杂度为 O(n)。

空间复杂度 : O(n),其中 n 为二叉树的节点个数。栈最多存储 n 个节点,因而须要额定的 O(n) 的空间。

第二题 对称二叉树

题目信息

解题思路


递归是解决树过程中最常见也是最简略的计划
从递归到迭代的转换方法

代码

func isSymmetric(root *TreeNode) bool {
    return check(root, root)
}

func check(p, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }
    if p == nil || q == nil {
        return false
    }
    return p.Val == q.Val && check(p.Left, q.Right) && check(p.Right, q.Left) 
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/symmetric-tree/solution/dui-cheng-er-cha-shu-by-leetcode-solution/
起源:力扣(LeetCode)
著作权归作者所有。商业转载请分割作者取得受权,非商业转载请注明出处。

复杂度剖析

工夫复杂度:这里遍历了这棵树,渐进工夫复杂度为 O(n)。
空间复杂度:这里的空间复杂度和递归应用的栈空间无关,这里递归层数不超过 n,故渐进空间复杂度为 O(n)。

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据