98.validate-binary-search-tree.md

题目地址

https://leetcode.com/problems/validate-binary-search-tree/description/

题目描述

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
 

Example 1:

    2
   / \
  1   3

Input: [2,1,3]
Output: true
Example 2:

    5
   / \
  1   4
     / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

思路

这道题是让你验证一棵树是否为二叉查找树（BST）。 由于中序遍历的性质如果一个树遍历的结果是有序数组，那么他也是一个二叉查找树(BST), 我们只需要中序遍历，然后两两判断是否有逆序的元素对即可，如果有，则不是BST，否则即为一个BST。

关键点解析

• 二叉树的基本操作（遍历）
• 中序遍历一个二叉查找树（BST）的结果是一个有序数组
• 如果一个树遍历的结果是有序数组，那么他也是一个二叉查找树(BST)

代码

/*
 * @lc app=leetcode id=98 lang=javascript
 *
 * [98] Validate Binary Search Tree
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    if (root === null) return true;
    if (root.left === null && root.right === null) return true;
    const stack = [root];
    let cur = root;
    let pre = null;

    function insertAllLefts(cur) {
        while(cur && cur.left) {
            const l = cur.left;
            stack.push(l);
            cur = l;
        }
    }
    insertAllLefts(cur);

    while(cur = stack.pop()) {
        if (pre && cur.val <= pre.val) return false;
        const r = cur.right;

        if (r) {
            stack.push(r);
            insertAllLefts(r);
        }
        pre = cur;
    }

    return true;
};

相关题目

230.kth-smallest-element-in-a-bst