二叉搜索树

BST (Binary Search Tree)

二叉搜索树性质：

对于任何节点x，如果有左子节点l，右子节点r，则l.val <= x.val，并且r.val >= x.val

所以在BST中，节点的左子树的所有节点的值都比它小（或相等），右子树的所有节点的值都比它大（或相等）。

二叉搜索树的有优点是，即便在最坏的情况下，也允许你在O(h)的时间复杂度内执行所有的搜索、插入、删除操作。

遍历

树的遍历分为：

• 前序遍历 / preorder tree walk
• 中序遍历 / inorder tree walk
• 后序遍历 / postorder tree walk

区别在于，如果用递归的方式遍历，那么访问根节点的顺序会不一样。

// 前序
console.log(root.val)
walk(root.left)
walk(root.right)

// 中序
walk(root.left)
console.log(root.val)
walk(root.right)

// 后序
walk(root.left)
walk(root.right)
console.log(root.val)

而二叉搜索树还有一个性质，当使用中序遍历时，得到的是一个升序的序列。

前驱和后继

对于节点x来说，前驱和后继就是中序遍历后，排在x前的节点叫前驱，排在x后的叫后继。

再具体一点，前驱就是x的左节点的最右子节点，后继就是x的右节点的最左子节点

树节点定义

Leetcode

 function TreeNode(val, left, right) {
     this.val = (val===undefined ? 0 : val)
     this.left = (left===undefined ? null : left)
     this.right = (right===undefined ? null : right)
 }

在《算法导论》中，还有p指针，指向的是节点的父节点。占用多一点空间，但是算法实现起来更简单。就像单链表和双链表。

LeetCode题

98. 验证二叉搜索树

二叉搜索树最重要的性质：

• 左节点所有的值小于等于根节点
• 右节点的所有值大于等于根节点

1. 递归

使用递归，我们必须得定义一个函数，对所有子树都适用。
但是我们左右子树判断不太一样，一个是<=，一个是>=。
所以我们这里用区间来统一这两种情况。

对于每个子树，他的边界都会相应的缩小，当递归每个子树都满足条件时，整颗树就是一个有效的二叉搜索树。

450. 删除节点

删除节点后还要保持二叉树的性质。我们分四种情况来分析。

1. 目标节点没有子节点
2. 目标节点只有一个左节点
3. 目标节点只有一个右节点
4. 目标节点左右节点都存在

前三种都很简单，相当于单链表的删除节点。

复杂的就是第四种情况。我们需要删除目标节点，并且找到它的前驱或者后继放到该位置。
以替换后继节点为例。

我们找到后继节点，删除掉该节点（它只可能有右节点），然后将删除的节点替换掉目标节点。

701. 插入节点

插入节点只需要判断需要传入的值和各个节点的值，比节点值大则往右边继续，否则往左边继续。

可以用递归也可以用迭代。

173. 迭代器

正常最简单的一次遍历我们采用的是递归。
但是我们可以用栈将递归转换为迭代。

1. 对于中序遍历来说，我们将当前节点先推入栈中。
2. 然后将当前节点的左节点推入栈。
3. 当前节点没有左节点时，将栈顶元素推出作为当前节点，迭代其值。
4. 然后将当前节点的右节点推入栈中，重复2。
5. 直到栈空并且当前节点为null

669. 验证平衡二叉树

平衡二叉树的性质为任何节点的左右子树的高度差不大于1。

递归算法：
计算并返回当前节点的高度。
分别获取左右子树的高度，判断高度差是否大于1。大于1则不是平衡树，返回-1（若子树高度返回-1则直接返回-1）。否则取子树的最大高度然后加1返回。递归完毕判断高度不为-1则是平衡二叉树。

841. 第K大节点

这里我们可以用数组或者树来保存这前K个节点。然后返回第K大的节点，数组通过下标，二叉搜索树则通过找最右子节点。

对比下性能：

• 数组的查找为O(1)，一次插入为O(k)
• 二叉树的查找为O(lg(k))，一次插入为O(lg(k))
• 堆/优先队列，查找为O(1)，一次插入为O(lg(k))

综上来看，使用堆来实现数据流的第K大节点是最理想的。

472. 最近公共祖先

求两个节点p，q的最近公共祖先，节点自己算自己的祖先。

1. 递归求通用的二叉树公共祖先

   1. 递归函数为返回匹配的p/q
   2. 如果左右子树同时返回不为null，则说明当前根节点就是最近公共祖先
   3. 如果左右子树有一个不为null，并且当前根节点匹配p/q，也说明当前节点为最近公共祖先
   4. 否则返回左右子树，当前根节点的匹配结果的或（即他们之中最多只存在一个匹配成功结果）

2. 使用二叉树性质简化

   1. 向下递归，找到第一个值在p和q中间的节点，就是他们的最近公共祖先

108. 将有序数组转换为高度平衡二叉搜索树

首先读题，有序数组和平衡二叉树。
要构建一个平衡二叉树，我们得保证左右子树高度差不大于1。

1. 再来看看有序数组给我提供了什么？我们能将数组从中间分开，保证左右子数组长度相差不大于1，保证了左右子树高度差不大于1。
2. 再用二叉搜索树性质，左子数组构建左子树，右子数组构建右子树，保证二叉搜索树的性质。