二叉树总结

递归返回值

1、如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。

2、如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 

3、如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。

从底向上遍历

需要从底向上遍历，那么二叉树，只能通过后序遍历（即：回溯）实现从底向上的遍历方式。在回溯的过程中，必然要遍历整棵二叉树，即使已经找到结果了，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的left和right）做逻辑判断。

二叉树遍历：前中后、层，递归，迭代（前中后用stk，使用null辅助，加入栈的顺序是反的；层序使用队列，按顺序入队出队）

完全二叉树（除了最后一列全满，最后一列只有左叶子结点）、平衡二叉树（每个结点的左子树和右子树高度相差小于等于1）、二叉搜索数（左边的所有值小于结点，右边的所有值大于结点）

求二叉树的深度（左子树和右子树的最大深度再加1）

二叉搜索树中的搜索（大于结点往右边搜，小于结点往左边搜）

二叉树的删除（没有右子树就直接返回root->left，有右子树遍历到右子树最左边的结点，和root swap值，再遍历左右子树删除）

二叉搜索树的删除（可以同上，也可以分析五种情况，利用二叉搜索树特性，多两个if判断需要遍历哪边子树删除）

从中序与后序遍历序列构造二叉树、从前序与中序遍历序列构造二叉树（构造二叉树一定要中序，后序和前序序列可以得到根结点，根节点再分割数组，递归返回构造结点，和结点的左右子树即可）

二叉树的最近公共祖先（递归的时候返回结点，告诉之前的结点找到的最近公共祖先是哪个，如果结点是空，或者结点=p或q就直接返回这个结点，遍历这个结点的左右子树，如果左右子树返回的结点不是空，那么返回这个结点，如果左子树返回值非空，右子树返回值空，返回左子树的结果，同理右子树，两个子树返回值都是空就直接返回空）

二叉搜索树的最近公共祖先（只要判断结点值是不是在pq之间就可以了，如果pq都小于结点值，返回遍历左边的值，都大于，遍历右边，else就直接返回当前结点）

二叉搜索树的插入（一定是可以插入到叶子结点的，遍历到null就新建结点并返回，当前值大于目标值，root->left = insert(root->left,val)，反之同样）

合并二叉树、二叉树对称性、翻转二叉树（同时处理左右子树，不要怼着根节点，重点在左右子树结点的处理逻辑）

二叉搜索树中的众数、最小绝对差（pre指针记住前一个结点的要记录的值，和当前结点比较，再更新pre指针）