BM34 判断是不是二叉搜索树

标签：right return BM34 int dfs 二叉 搜索 TreeNode root

思路： 对于这种dfs思想的算法，分三步走：

1. 先判断空节点
2. 再判断左子树和右子树
3. 根据左子树和右子树返回的信息以及当前节点的信息，返回最终的结果
4. 这里有一个技巧：用一个全局变量记录递归过程中出现不合法的情况，这样递归可以少返回一个值

  package main
import . "nc_tools" /* * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */
/** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param root TreeNode类 * @return bool布尔型 */ const ( INT_MAX = 1<<41 INT_MIN = -(1<<41) ) var res bool func getMax(left int,right int) int{ if left > right{ return left } return right } func getMin(left int,right int)int{ if left < right{ return left } return right } func dfs(root *TreeNode)(min int,max int){ //返回以root为根节点的二叉树的最小值，最大值,以及该二叉树是否是合法的搜索树 if root == nil{ return INT_MAX,INT_MIN } leftMin,leftMax := dfs(root.Left) rightMin,rightMax := dfs(root.Right) if root.Val <= leftMax || root.Val >= rightMin{ res = false }
min = getMin(leftMin,root.Val) max = getMax(rightMax,root.Val)
return min,max } func isValidBST( root *TreeNode ) bool { // write code here if root == nil{ return true } res = true _,_ = dfs(root) return res }

标签：right,return,BM34,int,dfs,二叉,搜索,TreeNode,root
From： https://www.cnblogs.com/starter-songudi/p/17088731.html