关于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)。