leetcode255. 验证前序遍历序列二叉搜索树

题目

给定一个整数数组，你需要验证它是否是一个二叉搜索树正确的先序遍历序列。

你可以假定该序列中的数都是不相同的。

参考以下这颗二叉搜索树：

5
    / \
   2   6
  / \
 1   3

示例

示例 1：

输入: [5,2,6,1,3]

输出: false

示例 2：

输入: [5,2,1,3,6]

输出: true

题解

二叉搜索树

首先我们应该要知道什么是二叉搜索树。二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： **若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。**二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。

简单来说，二叉搜索树就是就要以下特征的二叉树：

它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

前序遍历

先序遍历也叫做先根遍历、前序遍历，可记做根左右（二叉树父结点向下先左后右）。

首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。

解题思路

因为二叉搜索树具有“左子树上所有结点的值均小于它的根结点的值，右子树上所有结点的值均大于它的根结点的值”这个特点，所以我们可以从这个特点入手，如果可以找到左子树大于根节点或者右子树小于根节点的值，则说明该数组队列不满足二叉搜索树特点。

代码

/**
 * @param {number[]} preorder
 * @return {boolean}
 */
var verifyPreorder = function(preorder) {
    let q = [],flag = -Infinity;
    for(let p of preorder){
      //小于p的则可以判断为当前子树左子树节点和根节点，将其弹出，flag应该为当前数组的最小值
        while(q.length && q[0] < p) flag = q.shift();
        //flag大于p时为左子树节点大于右子树节点的情况，不满足二叉搜索树的特点，所以应该为false
        if(flag > p) return false;
        q.unshift(p);
    }
    return true;
};

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/verify-preorder-sequence-in-binary-search-tree

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。