前端怎么能不懂数据结构呢

数据结构在校园的教材、网上的课程中大部分都是以 C、C++语言为比如介绍，今天咱们就用 JavaScript 从头介绍一下基础数据结构：栈、行列、链表、树。

每种数据结构都会简单介绍一下其概念，并运用 JavaScript 完结，一起附上 leetcode 标题加深了解

栈

概念

• 遵从后进先出原则的有续调集
• 添加新元素的一端称为栈顶，另一端称为栈底
• 操作栈的元素时，只能从栈顶操作，如：添加元素、移除或取值

完结

需求完结的几个基本功能如下

• push：入栈办法
• pop: 出栈办法
• top：获取栈顶值
• size: 获取栈的元素个数
• clear: 清空栈

class Stack {
  constructor() {
    this.data = {};
    this.count = 0;
  }
  push(item) {
    this.data[this.count++] = item;
  }
  pop() {
    if (!this.size()) {
      return;
    }
    const top = this.data[this.count - 1];
    delete this.data[--this.count];
    return top;
  }
  top() {
    if (!this.size()) {
      return;
    }
    return this.data[this.count - 1];
  }
  size() {
    return this.count;
  }
  clear() {
    this.data = {};
    this.count = 0;
  }
}

栈的最小值

面试题 03.02. 栈的最小值

标题

界说栈的数据结构，请在该类型中完结一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时刻复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 回来 -3.
minStack.pop();
minStack.top();   --> 回来 0.
minStack.min();   --> 回来 -2.

提示：各函数的调用总次数不超越 20000 次

题解

var MinStack = function () {
  this.data = {};
  this.count = 0;
  this.minData = {};
  this.minCount = 0;
};
/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function (x) {
  this.data[this.count++] = x;
  if (!this.minCount || this.min() >= x) {
    this.minData[this.minCount++] = x;
  }
};
/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  if (this.top() === this.min()) {
    delete this.minData[--this.minCount];
  }
  delete this.data[--this.count];
};
/**
 * @return {number}
 */
MinStack.prototype.top = function () {
  return this.data[this.count - 1];
};
/**
 * @return {number}
 */
MinStack.prototype.min = function () {
  return this.minData[this.minCount - 1];
};

每日温度

739. 每日温度

标题

请依据每日 气温 列表 temperatures，从头生成一个列表，要求其对应方位的输出为：要想观测到更高的气温，至少需求等候的天数。假如气温在这之后都不会升高，请在该方位用 0 来替代。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73] 输出:[1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60] 输出:[1,1,1,0]

示例 3:

输入: temperatures = [30,60,90] 输出: [1,1,0]

提示：

• 1 <= temperatures.length <= 105
• 30 <= temperatures[i] <= 100

题解

常规办法：遍历，双层循环

单调栈：

• 由于要找升温的，所以咱们这儿反着来，规则栈是递减的
• 一开始栈是空的，第一个元素入栈；
• 第二个元素与栈顶比照，假如比栈顶值大，阐明找到了升温的一天，当时的索引减去栈顶的索引便是需求等候的时刻；一起栈顶值出栈，由于现已找到栈顶值升温等候的天数了，无需再处理它了；
• 这时分假如栈中还有值，持续拿当时值去与栈顶值比较，假如还是大于栈顶值，就重复上一步，假如小于栈顶值，就将当时值入栈，循环取下一个值来持续比较

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
  const stack = [temperatures[0]];
  const len = temperatures.length;
  const arr = new Array(len).fill(0);
  for (let i = 0; i < len; i++) {
    const curtemp = temperatures[i];
    while (stack.length && curtemp > stack[stack.length - 1]) {
      // 也能够将 stack 改成存索引，这儿就不用再 findIndex 了
      const stackIndex = temperatures.findIndex(
        (cur) => cur === stack[stack.length - 1]
      );
      arr[stackIndex] = i - stackIndex;
      stack.pop();
    }
    stack.push(curtemp);
  }
  return arr;
};

行列

概念

• 遵循先进先出的有序调集
• 添加新元素的一端为队尾，另一端为队首

完结

依据数组完结

class Queue {
  constructor() {
    this.queue = [];
    this.count = 0;
  }
  // 入队
  enQueue(item) {
    this.queue[this.count++] = item;
  }
  // 出队
  deQueue() {
    if (this.isEmpty()) {
      return;
    }
    this.count--;
    return this.queue.shift();
  }
  // 是否为空
  isEmpty() {
    return this.count === 0;
  }
  // 队首元素
  top() {
    if (this.isEmpty()) {
      return;
    }
    return this.queue[0];
  }
  length() {
    return this.count;
  }
  clear() {
    this.count = 0;
    this.queue = [];
  }
}

依据目标完结

class Queue {
  constructor() {
    this.queue = {};
    this.count = 0;
    this.head = 0;
  }
  // 入队
  enQueue(item) {
    this.queue[this.count++] = item;
  }
  // 出队
  deQueue() {
    if (this.isEmpty()) {
      return;
    }
    const headData = this.queue[this.head];
    delete this.queue[this.head];
    this.head++;
    return headData;
  }
  length() {
    return this.count - this.head;
  }
  // 是否为空
  isEmpty() {
    return this.length() === 0;
  }
  clear() {
    this.queue = [];
    this.count = 0;
    this.head = 0;
  }
}

双端行列

双端行列（double-ended queue）指的是允许一起从队尾与队首两头进行存取操作的行列，操作更加灵敏

基本功能如下：

• addFront：从头添加元素
• addBack：从尾部添加元素
• removeFront：删去头部元素
• removeBack：删去结尾元素
• frontTop：获取头部元素
• backTop：获取结尾元素

class Deque {
  constructor() {
    this.queue = {};
    this.count = 0;
    this.head = 0;
  }
  addFront(item) {
    this.queue[--this.head] = item;
  }
  addBack(item) {
    this.queue[this.count++] = item;
  }
  removeFront() {
    if (this.isEmpty()) {
      return;
    }
    const front = this.queue[this.head];
    delete this.queue[this.head++];
    return front;
  }
  removeBack() {
    if (this.isEmpty()) {
      return;
    }
    const back = this.queue[this.count - 1];
    delete this.queue[--this.count];
    return back;
  }
  frontTop() {
    if (this.isEmpty()) {
      return;
    }
    return this.queue[this.head];
  }
  backTop() {
    if (this.isEmpty()) {
      return;
    }
    return this.queue[this.count - 1];
  }
  length() {
    return this.count - this.head;
  }
  isEmpty() {
    return this.length() === 0;
  }
}

行列的最大值

标题

请界说一个行列并完结函数 max_value 得到行列里的最大值，要求函数 max_value、push_back 和 pop_front 的均摊时刻复杂度都是 O(1)。

若行列为空，pop_front 和 max_value 需求回来 -1

示例 1：

输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出:[null,null,null,2,1,2]

示例 2：

输入:
["MaxQueue","pop_front","max_value"]
[[],[],[]]
输出:[null,-1,-1]

限制：

• 1 <= push_back,pop_front,max_value 的总操作数 <= 10000
• 1 <= value <= 10^5

题解

var MaxQueue = function () {
  this.queue = {};
  this.count = 0;
  this.head = 0;
  this.dque = {};
  this.dcount = 0;
  this.dhead = 0;
};
/**
 * @return {number}
 */
MaxQueue.prototype.max_value = function () {
  return this.dque[this.dhead];
};
/**
 * @param {number} value
 * @return {void}
 */
MaxQueue.prototype.push_back = function (value) {
  this.queue[this.count++] = value;
  if (!this.dque[this.dhead]) {
    this.dque[this.dhead] = value;
  } else if (value > this.dque[this.dhead]) {
    this.dque[this.dhead--] = value;
  }
};
/**
 * @return {number}
 */
MaxQueue.prototype.pop_front = function () {
  if (this.count === this.head) {
    return -1;
  }
  const front = this.queue[this.head];
  delete this.queue[this.head++];
  return front;
};

滑动窗口的最大值

239. 滑动窗口最大值

标题

给定一个数组 nums 和滑动窗口的巨细 k，请找出一切滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解说:

滑动窗口的方位                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

提示：

你能够假定 k 总是有用的，在输入数组 不为空 的状况下，1 ≤ k ≤ nums.length。

题解

/**
 * @param {number[]} nums 传入数组
 * @param {number} k 滑动窗口宽度
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  if (k <= 1) {
    return nums;
  }
  const result = [];
  const deque = [];
  // 1、将窗口第一个方位的数据添加到 deque 中，坚持递减
  deque.push(nums[0]);
  let i = 1;
  for (; i < k; i++) {
    // deque存在数据
    // 当时数据大于队尾值
    // 出队，再重复比较
    while (deque.length && nums[i] > deuqe[deque.length - 1]) {
      deque.pop();
    }
    deque.push(nums[i]);
  }
  // 将第一个方位的最大值添加到result
  result.push(deque[0]);
  // 2、遍历后续数据
  for (; i < nums.length; i++) {
    while (deque.length && nums[i] > deuqe[deque.length - 1]) {
      deque.pop();
    }
    deque.push(nums[i]);
    // 检测当时最大值是否位于窗口外
    if (deque[0] === nums[i - k]) {
      deque.shift();
    }
    // 添加最大值到result
    result.push(deque[0]);
  }
};

链表

链表是有序的数据结构

与栈、行列的区别便是：链表能够从首、尾、中心任一方位进行数据存取，灵敏度更高一些

到这儿你或许就会有疑问了，这直接用数组不就完了？

为什么不直接用数组？

原因很简单，在做某些操作时，链表的功能优于数组

数组是用来存有序数据的一种数据类型，在内存中需求占用一段接连的空间；也由于它占用的空间是接连的，所以咱们能够直接运用索引快速找到对应的元素；当咱们对数组进行添加或者移除操作时，就或许呈现功能开销比较大的状况，例如在非结尾的方位添加、移除元素，就会导致后续的元素呈现位移。

直接用数据说话，这是两段操作数组的代码，

const arr = [];
for (let i = 0; i < 100000; i++) {
  arr.push(i);
}

const arr = [];
for (let i = 0; i < 100000; i++) {
  arr.unshift(i);
}

借助 jsbench 工具，得到两段代码的履行效率如下：

• push 操作：1112 ops/s
• unshift 操作：2.9 ops/s

(JSBench 的运用欢迎看我这一篇文章 ☞ js 功能优化（实战篇）)

概念

• 链表是有序的数据结构
• 链表中的每个部分称为节点
• 能够从首、尾、中心进行数据存取
• 链表的元素在内存中不必是接连的空间

优势

添加与删去操作不会导致其他元素的位移，首要运用场景是一些常常需求添加、删去元素的数据

劣势

无法依据索引快速定位元素

完结

由于链表在内存中并不需求是接连的，所以咱们这儿运用 next 标记链表中的下一个元素

这儿咱们完结两个类：

• 节点类：value、next
• 链表类
  • addAtTail 尾部添加节点
  • addAtHead 头部添加节点
  • addAtIndex 指定方位添加节点
  • get 读取节点
  • removeAtIndex 删去指定方位的节点

// 节点类
class LinkedNode {
  value: unknown;
  next: null | LinkedNode;
  constructor(val: unknown) {
    this.value = val;
    this.next = null;
  }
}

// 链表类
class LinkedList {
  count: number;
  head: null | LinkedNode;
  constructor() {
    // 节点个数
    this.count = 0;
    // 头部“指针”
    this.head = null;
  }
  // 尾部添加节点
  addAtTail(val: unknown) {
    const node = new LinkedNode(val);
    if (!this.count || !this.head) {
      // 链表为空
      this.head = node;
      this.count++;
      return;
    }
    // 链表有数据
    let cur = this.head;
    // 循环查找尾部节点
    while (cur.next) {
      cur = cur.next;
    }
    // 将新节点添加到结尾
    cur.next = node;
    this.count++;
  }
  // 头部添加节点
  addAtHead(val: unknown) {
    const node = new LinkedNode(val);
    if (this.count) {
      // 链表不为空
      node.next = this.head;
    }
    this.head = node;
    this.count++;
  }
  // 指定方位添加节点
  addAtIndex(index: number, val: unknown) {
    const node = new LinkedNode(val);
    const target = this.get(index);
    if (!target) {
      return false;
    }
    node.next = target;
    const prev = this.get(index - 1);
    if (prev) {
      prev.next = node;
    }
    return true;
  }
  // 依据索引获取节点
  get(index: number) {
    if (!this.count || index < 0 || index >= this.count || !this.head) {
      /**
       * 异常数据处理
       * 1. 链表为空
       * 2. index 为负数
       * 3. index 超出链表范围
       * 4. head 为 null
       */
      return null;
    }
    // 从首部开始向后获取节点
    let target = this.head;
    let count = 0;
    while (target.next && count < index) {
      /**
       * 存在下一个节点
       * 且还未抵达指定方位
       */
      target = target.next;
      count++;
    }
    if (index === count) {
      return target;
    }
    return null;
  }
  // 删去指定方位的节点
  removeAtIndex(index: number) {
    const target = this.get(index);
    if (!target) {
      return false;
    }
    const prev = this.get(index - 1);
    if (prev) {
      prev.next = target.next;
    }
    return true;
  }
}

链表类型

双向链表

指在一般链表的基础上，添加一个用于记载上一个节点的属性 prev，可进行双向拜访。

首节点的 prev 指向空，结尾节点的 next 指向空。

循环链表

又称 “环形链表”，指的是链表最终一个节点的 next 指向第一个节点，形成首尾相连的循环结构。

实际运用中，最终一个节点的 next 不一定要指向第一个节点，或许是链表中任一方位的节点。

回转链表

LeetCode 206.回转链表

标题

回转一个单链表。

示例：

输入：1->2->3->4->5->NULL
输出：5->4->3->2->1->NULL

进阶：你能够迭代或递归地回转链表。你能否用两种方法处理这道题？

题解

/**
 * Definition for singly-llinked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null :: next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let cur = head;
  let prev = null;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
};

递归解法

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  if (!head || !head.next) {
    return head;
  }
  const newHead = reverseList(head.next);
  // 第一次履行这儿的节点是倒数第二个节点
  head.next.next = head;
  // head 的 next 在下一次递归时会被从头设置
  // 最终一次的 next 会被设置为 null
  head.next = null;
  return newHead;
};

环路检测

面试题 02.08. 环路检测

标题

给定一个链表，假如它是有环链表，完结一个算法回来环路的最初节点。若环不存在，请回来 null。

假如链表中有某个节点，能够经过接连盯梢 next 指针再次抵达，则链表中存在环。 为了表明给定链表中的环，咱们运用整数 pos 来表明链表尾连接到链表中的方位（索引从 0 开始）。 假如 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际状况。

示例 1：

输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解说：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0 输出：tail connects to node index 0 解说：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1 输出：no cycle 解说：链表中没有环。

进阶：

你是否能够不用额定空间处理此题？

题解：哈希表

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function (head) {
  const visited = new Set();
  while (head !== null) {
    if (visited.has(head)) {
      return head;
    }
    visited.add(head);
    head = head.next;
  }
  return null;
};

题解：快慢指针

• slow 指针，每次移动一位
• fast 指针，每次移动两位

fast 移动的距离是 slow 的两倍，因而假如链表中存在环，那么 fast 与 slow 必定会相遇

var detectCycle = function (head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (!fast) {
      return null;
    }
    if (slow === fast) {
      // 存在环路
      let ptr = head;
      /**
       * 新指针 ptr 从 head 开始移动
       * slow 持续移动
       * ptr 与 slow 相遇的方位即为环的起点
       */
      while (ptr.next) {
        if (ptr === slow) {
          return ptr;
        }
        ptr = ptr.next;
        slow = slow.next;
      }
    }
  }
  return null;
};

树与二叉树

树的概念

栈、行列都归于线性结构，而树归于非线性结构

树中每个部分被称为结点，节点之间存在分支结构与层次联系

每个树形结构都具有一个根结点，如下图中的 A 结点

依据节点之间的联系，还存在 父结点、子结点、兄弟结点

不含子结点的结点称为 叶结点，如上图中的 D、E、F

以树的视点，还存在 子树 的概念，指的是对某个结点与其子孙结点的总称

B、D、H 就能够看作是子树

由于树存在父子联系，树的结点形成了多级结构，每一层被称为 层级

从根结点开始，根结点的层级为 1，向下顺次递加

最深结点的层级被称为树的 高度，上图中树的高度便是 3

二叉树的概念

树结构中的一种，二叉树的每个结点最多只能存在两个子结点

二叉树中子结点有更明确的称呼，左子结点 与 右子结点

还有一些特别方法的二叉树，如：满二叉树、彻底二叉树

• 满二叉树：每层结点都到达最大值
• 彻底二叉树：除了最终一层外，每层结点都到达最大值，且最终一层结点都位于左边

二叉树的存储方法

首要有两种：次序存储方法、链式存储方法

次序存储方法首要是彻底二叉树和满二叉树运用，由于它的结构是接连的，能够依照从左到右、从上到下的次序将结点存储在数组中；

关于一般二叉树也能够运用次序存储，不存在的结点能够运用 null 等空值替代，但是对存储空间是一种糟蹋；

因而，一般二叉树一般采用链式存储方法，记载结点间的联系，每个结点经过 value 表明值，left、right 表明左右子结点

二叉树的遍历

依据拜访次序的不同，有三种不同的遍历方法：前序遍历、中序遍历、后序遍历

• 前序遍历：根结点 -> 左子树 -> 右子树
• 中序遍历：左子树 -> 根结点 -> 右子树
• 后序遍历：左子树 -> 右子树 -> 根结点

二叉树的前序遍历

144. 二叉树的前序遍历

标题

给你二叉树的根节点 root ，回来它节点值的 前序 遍历。

示例 1：

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

示例 2：

输入：root = [] 输出：[]

示例 3：

输入：root = [1] 输出：[1]

示例 4：

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

示例 5：

输入：root = [1,null,2] 输出：[1,2]

提示：

• 树中节点数目在范围 [0, 100] 内
• -100 <= Node.val <= 100

进阶：递归算法很简单，你能够经过迭代算法完结吗？

题解：递归方法

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function (root) {
  if (!root) {
    return [];
  }
  return [
    root.val,
    ...preorderTraversal(root.left),
    ...preorderTraversal(root.right),
  ];
};

题解：迭代方法

var preorderTraversal = function (root) {
  const result = [];
  const stack = [];
  while (root || stack.length) {
    while (root) {
      stack.push(root.right);
      result.push(root.val);
      root = root.left;
    }
    root = stack.pop();
  }
  return result;
};

二叉树的最大深度

104. 二叉树的最大深度

标题

给定一个二叉树 root ，回来其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

示例 1：

输入：root = [3,9,20,null,null,15,7] 输出：3

示例 2：

输入：root = [1,null,2] 输出：2

提示：

• 树中节点的数量在 [0, 104] 区间内。
• -100 <= Node.val <= 100

题解：深度优先查找（DFS）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function (root) {
  if (!root) {
    return 0;
  }
  return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
};

二叉树的层序遍历

102. 二叉树的层序遍历

标题

给你二叉树的根节点 root ，回来其节点值的 层序遍历 。 （即逐层地，从左到右拜访一切节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1] 输出：[[1]]

示例 3：

输入：root = [] 输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

题解：广度优先查找（BFS）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function (root) {
  const result = [];
  if (!root) {
    return result;
  }
  // 声明行列，缓存一下同层的结点
  const q = [root];
  while (q.length) {
    result.push([]);
    const len = q.length;
    // 遍历行列，读取同层结点
    for (let i = 0; i < len; i++) {
      const node = q.shift();
      result[result.length - 1].push(node.val);
      // 假如还存在左右子结点，存入行列中
      if (node.left) {
        q.push(node.left);
      }
      if (node.right) {
        q.push(node.right);
      }
    }
  }
  return result;
};

二叉查找树

一种特别的二叉树方法，简称 BST

左子树的结点小于根结点，右子树的结点大于根结点

子树也是二叉查找树

验证二叉查找树

98. 验证二叉查找树

标题

给你一个二叉树的根节点 root ，判别其是否是一个有用的二叉查找树。

有用 二叉查找树界说如下：

• 节点的左子树只包括 小于 当时节点的数。
• 节点的右子树只包括 大于 当时节点的数。
• 一切左子树和右子树自身必须也是二叉查找树。

示例 1：

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

示例 2：

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

提示：

• 树中节点数目范围在 [1, 104] 内
• -231 <= Node.val <= 231 - 1

题解：递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function (root) {
  return helper(root, -Infinity, Infinity);
};
const helper = (root, lower, upper) => {
  if (!root) {
    return true;
  }
  if (root.val >= upper || root.val <= lower) {
    return false;
  }
  return (
    helper(root.left, lower, root.val) && helper(root.right, root.val, upper)
  );
};

题解：中序遍历

以上图的二叉查找树为例，假如是用中序遍历，遍历的成果如下：

[3, 7, 9, 10, 12, 15]

能够明显看出，得到的成果便是递加数组

先来个中序遍历算法

var inorderTraversal = function (root) {
  const stack = [];
  const result = [];
  while (root || stack.length) {
    while (root) {
      // 先将根结点入栈
      stack.push(root);
      // 移动到左子结点，持续入栈
      root = root.left;
    }
    /**
     * 走到这
     * stack 中缓存了左子结点和根结点
     * 3、7、10
     */
    root = stack.pop();
    result.push(root.val);
    // 移动到右结点
    root = root.right;
  }
  return result;
};

经过中序遍历得到了 result，接下来只需判别一下 result 是不是递加

var isValidBST = function (root) {
  const stack = [];
  const result = [];
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    if (result[result.length - 1] >= root.val) {
      /**
       * 判别下一个结点是否大于上一个结点
       * 为 false 就代表 result 不是递加的
       */
      return false;
    }
    result.push(root.val);
    root = root.right;
  }
  return true;
};

咱们看到这个时分 result 就显的有点多余了，咱们只需求比照上一个结点罢了，不需求记载一切结点的值，再改造一下

var isValidBST = function (root) {
  const stack = [];
  let last = -Infinity;
  while (root || stack.length) {
    while (root) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    if (last >= root.val) {
      return false;
    }
    last = root.val;
    root = root.right;
  }
  return true;
};

以上，便是前端视角下的基础数据结构；今年来行业不景气，趁此机会好好充分一下自己吧