关于算法: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/probl…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。