第一题 验证二叉搜寻树
题目信息
解题思路
所有左子树和右子树本身必须也是二叉搜寻树。
显然这能够用递归的形式解决
咱们只需验证根节点的值大于所有左子树的值，小于所有右子树的值即可
即 将根节点别离与左子树的最大节点，根节点与右子树的最小节点比拟
代码如下
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)。