[数据结构与算法]判断是否是二叉平衡树

思路： 中序遍历二叉树，判断遍历节点值是否递增顺序

type Node struct {
	left  *Node
	right *Node
	val   int
}

/*
 判断是否二叉搜索树
    根节点> 左子树，右子树> 根节点
*/

func IsBST(root *Node, list []int) (bool, []int) {
	if root == nil {
		return true, list
	}

	isLeft, leftList := IsBST(root.left, list)
	if !isLeft {
		return false, nil
	}
	if len(leftList) > 0 && root.val < leftList[len(leftList)-1] {
		return false, nil
	}
	leftList = append(leftList, root.val)
	isRight, rightLeftList := IsBST(root.right, leftList)
	if !isRight {
		return false, nil
	}

	return true, rightLeftList
}

func IsBST2(root, pre *Node) (bool, *Node) {
	if root == nil {
		return true, pre
	}

	isLeft, pre := IsBST2(root.left, pre)
	if !isLeft {
		return false, nil
	}
	if pre != nil && root.val < pre.val {
		return false, nil
	}
	pre = root
	isRight, pre := IsBST2(root.right, pre)
	if !isRight {
		return false, nil
	}

	return true, pre
}