初级算法-树-验证二叉搜索树

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

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

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

摘一个示例做个说明.
示例 1：
输入:
    2
   / \
  1   3
输出: true

条件分析:

1. 树操作 -> 先考虑处理方式: 数组、map、递归、循环、链表etc
2. 有效的二叉搜索树 -> 大于左,小于右
3. 所有左子树和右子树自身必须也是二叉搜索树 -> 大于所有左,小于所有右

解决思路1:

1. 根据分析1,采用递归操作,一般树都是采用递归.数组和map不适合,基本上都是从循环还是递归选.
2. 根据分析2,需要保证本身处于区间值内
   根据分析3,需要保证本身处于自身区间和节点相应区间

先设定区间为数据最小值和数据最大值.直接采用Int min和max.然后判断树是否存在.

如果存在则判断左右值是否在区间内.如果不在,则直接返回false.如果在,则继续进行递归.直到返回结果.

// 验证二叉搜索树
func isValidBST(_ root: TreeNode?) -> Bool {
    return isValidBST(root, Int.min, Int.max)
}

func isValidBST(_ root: TreeNode? ,_ min: Int, _ max: Int) -> Bool{
    //如果不存在则返回true
    guard let tree = root else {
        return true
    }
    //节点值大于最大值 或者小于最小值(区间)
    if tree.val >= max || tree.val <= min {
        return false
    }
    //归根结底还是需要递归
    return isValidBST(tree.left, min, tree.val) && isValidBST(tree.right, tree.val, max)
}

验证二叉搜索树 提交结果.jpg

测试用例:

let tree = TreeNode()
tree.val = 10
tree.left = TreeNode()
tree.left?.val = 5
tree.right = TreeNode()
tree.right?.val = 11
tree.left?.right = TreeNode()
tree.left?.right?.val = 6

tree.left?.right?.left = TreeNode()
tree.left?.right?.left?.val = 7

tree.right?.right = TreeNode()
tree.right?.right?.val = 13

考察要点:

• 树
• 深度搜索优先
• 广度搜索优先
• 二叉树