【golang】leetcode初级-验证二叉搜索树&对称二叉树【golang】leetcode初级-验证二叉

第一题验证二叉搜索树题目信息

文章图片

解题思路
所有左子树和右子树自身必须也是二叉搜索树。
显然这可以用递归的方式解决
我们只需验证根节点的值大于所有左子树的值，小于所有右子树的值即可
即将根节点分别与左子树的最大节点，根节点与右子树的最小节点比较
代码如下

func isValidBST(root *TreeNode) bool { if root.Left==nil && root.Right==nil{ return true } if root.Valmin(root){ returnfalse }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）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

复杂度分析
【【golang】leetcode初级-验证二叉搜索树&对称二叉树】时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)。
空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。