数据结构与算法之二叉树: Leetcode 98. 验证二叉搜索树 (Typescript版)-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构与算法之二叉树: Leetcode 98. 验证二叉搜索树 (Typescript版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/

描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树
有效二叉搜索树定义如下：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。

示例 1

      2
     / \
    1    3

输入：root = [2,1,3]
输出：true

示例 2

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示

树中节点数目范围在[1, $10^4$ ] 内
- $2^{31}$ <= Node.val <= $2^{31}$ - 1

算法实现

1 ）方案 1

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isValidBST(root: TreeNode | null): boolean {
  // 1. 声明最终存储树的数组
  const traversalArr: number[] = [];
  // 2. 定义基于中序遍历获取最终数组算法
  function inorderTraverse(root: TreeNode | null): void {
    if (!root) return;
    inorderTraverse(root.left);
    traversalArr.push(root.val);
    inorderTraverse(root.right);
  }
  // 3. 开始中序遍历
  inorderTraverse(root);
  // 4. 验证当前数组是否符合要求
  for (let i = 0, length = traversalArr.length; i < length - 1; i++) {
    if (traversalArr[i] >= traversalArr[i + 1]) return false;
  }
  return true;
};

此方案是官方提供算法，用到了中序遍历的特性，它先遍历左子树，再遍历根节点，最后遍历右子树
而我们二叉搜索树保证了左子树的节点的值均小于根节点的值，根节点的值均小于右子树的值
因此中序遍历以后得到的序列一定是升序序列
最终进行验证的for循环就是检验是否是升序序列, 最终得到是否符合要求
这里有一个优化点是：最终保留了整个中序遍历的数组，实际上是不需要的
每一步最后添加的元素就足以知道是或不是二叉搜索树了，请看方案2

2 ）方案 2文章来源地址https://www.toymoban.com/news/detail-603289.html

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isValidBST(root: TreeNode | null): boolean {
    let stack = []; // 存储的是未拜访过的树中的节点的值
    let inorder = -Infinity; // 存储上一个中序遍历到的树节点值

    while (stack.length || root) {
    	// 不断将当前树节点的左子节点加入栈, 直到没有左节点
        while (root) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop(); // 将当前子树最左边的节点从栈中取出
        // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
        if (root.val <= inorder) {
            return false;
        }
        inorder = root.val; // 将当前节点的值设为 inorder
        root = root.right; // 将当前右子节点作为根节点，继续遍历
    }
    return true;
};