树

「树」，用数组实现就是「堆」，因为「堆」是一个完全二叉树，用数组存储不需要节点指针，操作也比较简单；用链表实现就是很常见的那种「树」，因为不一定是完全二叉树，所以不适合用数组存储。为此，在这种链表「树」结构之上，又衍生出各种巧妙的设计，比如二叉搜索树、AVL 树、红黑树、区间树、B 树等等，以应对不同的问题。

二叉树

• 遍历
  1.深度搜索：前中后序遍历：根与左右子树的顺序。

preOrderTravese{
 前序： do something with the root;
  travese(root.left);
  traverse(root.right);
}

InOrderTravese{
  travese(root.left);
   中序：do something with the root;
  traverse(root.right);
}

postOrderTravese{
  travese(root.left);
  traverse(root.right);
 后序：do something with the root;
}

2. 广度搜索：层序遍历。

• 如何序列化出二叉树的所有子树？
• preOrderTravese：root+","+leftvalue+","+rightvalue，空为#
• postOrderTravese: leftvalue+","+rightvalue+","+root，空为#
• 当左右子树一致时，中序不ok

BST二叉搜索树

概念

1.BST的定义，左子树<root<右子树，不单单是左右子树的根，是整棵树。
2.任意二叉树，一定含有BST树，因为单个叶子就是BST，同样的：1<2<null也是BST树

• 1373. 二叉搜索子树的最大键值和 - 力扣（LeetCode） (leetcode-cn.com)

性质

1.BST 的中序遍历结果是有序的（升序），BST逆中序遍历就是降序。

• 力扣538 将二叉树转为大于等于节点的累加和之树