看卡哥视频 关于树

完全二叉树？1. 除了底层，其他层都是满的；2.底层空的点都在右边，底层是连续的

满二叉树？叶节点不缺，满的

二叉搜素树？对所有节点，他的左树的所有节点都小于他；右树的所有节点都大于他

平衡二叉搜索树？左树和右树的高度差接近，绝对值小于1。用处很大：map, set, multi_map, multi_set, log n 插入和查询。note: unordered_map和unordered_set底层是hash table

二叉树咋存储的？

链性和线性的

2 * i + 1 数组里第i个节点的左节点的下标

2 * i + 2 数组里第i个节点的右节点的下标

遍历

深度优先

用递归和stack

前中后序：中 左子树 右子树，左子树 中 右子树，左子树 右子树 中

前和中序唯一确定一棵二叉树：

广度优先

用队列

struct TreeNode {

int val;

TreeNode * left;

TreeNode* right;

TreeNode*(int val)" val(val), left(NULL), right(NULL) {

}

}