树和图

理论

链表是特殊的树(后继节点可以多个),树是特殊的图(可以乱指)。

二叉搜索树(binary search tree):有序二叉树、排序二叉树,是指一棵空树或具有下列性质的二叉树:

  1. 左子树上所有节点的值都小于它的根节点的值。
  2. 右子树上所有节点的值都大于它的根节点的指。
  3. recursively,坐、右子树也分别为二叉搜索树。

时间复杂度是O(logN),最差是O(n),比如只有右子节点,就是一个链表了。

验证二叉排序树

validate BST,leetcode 98 题。

  1. in-order 中序遍历(左、根、右),应该是一个升序的 array。
  2. 递归