二叉树
二叉搜索树
特点：一般用中序遍历
性质：中序遍历会得到一个单调递增的序列
leetcode 2476
中序遍历得到递增序列，对于每个询问做一次二分查找，时间复杂度O(n*logn)
leetcode 1932
需要观察出两个性质：
1、根节点是唯一的
2、合并方式是唯一的
1解释：一棵树能成为根节点，说明它没有出现在任何叶子节点上，无法“被”合并，如果不是唯一的，最后不可能合并成一棵树
2解释：一棵树如果能被多个叶子节点合并，假设最后能合并成一棵树，必然会有值相同的节点，不符合二叉搜索树的性质
理解上面两个性质，可以得到做法如下：
1、先找到最终树的根节点，这个根节点必然没有出现在任何叶子上，有且只有一个
2、中序遍历：
非叶节点正常遍历；
遍历到叶节点，把合适的树连接过来，找树的过程可以用哈希表优化到O(1)，然后继续中序遍历，同时需要保证中序遍历结果符合二叉搜索树性质：值必须递增。
时间、空间复杂度O(n)
leetcode 1373
二叉搜索树一般是中序遍历，但是这题不行，因为找的必须是一颗完整的子树（中序遍历只能得到残缺的子树）。
那就要求我们在判断二叉搜索树的同时必须知道这颗子树的节点和
由此不难想到必须从底向上遍历：用后序遍历判断二叉搜索树，同时多传一个值表示子树节点和。后续遍历不会可以去做leetcode 98
创建二叉树
leetcode 1382
二叉搜索树转平衡的二叉搜索树。中序遍历得到递增节点，每次取中点建树。
最近公共祖先
leetcode 236
普通二叉树LCA，用分类讨论的方式思考：
1、遍历到空节点，返回节点本身（root）
2、遍历到p、q，不需要继续遍历，另一个节点要么在它子树中，要么在它祖先的另一侧，这两种情况都返回节点本身（root）
3、p、q在左右子树，返回当前节点（root）
4、p、q在左子树，返回左子树（root.left）
5、p、q在右子树，返回右子树（root.right）
6、左右子树都没找到（返回空）
需要遍历整个树，时间复杂度O(n)
leetcode 235
二叉搜索树LCA，用普通二叉树的方式思考是可以的，复杂度O(n)
考虑二叉搜索树性质（左子树值全部小于当前节点，右子树值全部大于当前节点），不需要递归整棵子树，根据节点值的大小分类讨论：
1、因为题目保证p、q一定存在，所以不会遍历到空节点
2、遍历到p、q，不需要继续遍历，另一个节点一定在它子树中（在它祖先的另一侧的情况被二叉搜索树排除），这两种情况都返回节点本身（root）
3、p、q在左右子树（val判断），返回当前节点（root）
4、p、q在左子树（val判断），返回左子树递归结果
5、p、q在右子树（val判断），返回右子树递归结果
时间复杂度O(h)，h为二叉搜索树高度，因为我们只需要沿着一条路径查找。但是二叉搜索树可能退化为链表，此时h == n，最坏时间复杂度O(n)
leetcode 1676
求k个节点的lca，如果还是两个两个点求，时间复杂度O(k*n)
可以把数组转成集合，每次递归用O(1)的时间复杂度判断当前节点是否在集合内，在集合内返回当前节点，其他分析和写法和两个点的情况完全一样
二叉树BFS
leetcode 2471
按层遍历二叉树，重点是怎么求最小交换次数。
先离散化，从头扫一遍，对于每个位置，如果不在自己正确的位置则看它正确的位置是什么数，这样最终会找到一个环（集合），最小交换次数是环大小减一。
找环的时间复杂度是O(n)，离散化需要排序，时间复杂度O(nlogn)，整体时间复杂度O(nlogn)
二叉树直径
leetcode 543
定义题，分析得到：经过一个节点的最长链等于左子树最长链+右子树最长链+2，所以在求左右子树最长链的同时更新直径即可。需要注意最长链不一定经过根节点。