验证二叉搜索树

1. 题目描述

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。

2. 思路

1. 思路一
   • 中序遍历转换成数组
   • 校验数组是否升序的
2. 思路二
   • 中序遍历，判断当前节点是否大于中序遍历的前一个节点

3. 实现

3.1. 中序遍历

func isValidBST(root *TreeNode) bool {
	if root == nil {
		return true
	}

	res := make([]int, 0)
	midOrder(root, &res)
	for i := 0; i < len(res)-1; i++ {
		if res[i] >= res[i+1] {
			return false
		}
	}

	return true
}

func midOrder(root *TreeNode, res *[]int) {
	if root == nil {
		return
	}

	midOrder(root.Left, res)
	*res = append(*res, root.Val)
	midOrder(root.Right, res)
}

3.2. 遍历过程中记录上一个值

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isValidBST(root *TreeNode) bool {
    pre := &TreeNode{Val:math.MinInt64}
    return dfs(root, &pre)
}

func dfs(root *TreeNode, pre **TreeNode) bool {
    if root == nil {
        return true
    }

    if flag := dfs(root.Left, pre); !flag {
        return false
    }
    if (*pre).Val >= root.Val {
        return false
    }
    *pre = root
    if flag :=  dfs(root.Right, pre); !flag {
        return false
    }
    return true
}

4. 参考

• 中序遍历轻松拿下，🤷‍♀️必须秒懂！ - 验证二叉搜索树 - 力扣（LeetCode）