题解 | #判断一棵满二叉树是否为二叉搜索树#

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

//主要思想，二叉搜索树应满足中序遍历（左中右）时，节点值单调递增
var pre,res=-1,true//pre为负数，所以第一轮无论根节点多小pre都会被更新；res为true是为了应对开局即出界的情况
func isTree(nums []int,i int) bool {
	n := len(nums)
    if i>=n{return res}//出界
    isTree(nums,i<<1+1)//按照中序遍历，先查左子树
    if nums[i]<=pre{res=false;return res}//按照中序遍历，查当前根，如果当前节点的值小于上一节点的值，则违反递增，return false
    pre=nums[i]//如果当前根没有违反递增，则继续向后查
    isTree(nums,i<<1+2)//按照中序遍历原则，最后查右子树
    return res
}

func main() {
	input := bufio.NewScanner(os.Stdin)
	input.Scan()
	str := strings.Split(input.Text(), ",")
	arr := []int{}
	for _, v := range str {
		i, _ := strconv.Atoi(v)
		arr = append(arr, i)
	}
    var ans string
    if isTree(arr,0) {
        ans= "True"
    }else{
        ans= "False"
    }
	fmt.Println(ans)
}