7.14 树

leetcode 两树合并为一树

思路：根节点的合并与左右子树的合并是一样的，所以可以使用递归。以其中一棵树作为返回树。注意递归返回条件。

leetcode 求树的最大深度

思路：递归，用1+左右子树最大深度的最大值，要先写递归返回条件

leetcode 反转树

思路：递归返回条件，先把左子树存下来，然后依次反转左右子树。

leetcode 求二叉树的直径，直径是从某节点到某节点的最长路径，一条边算1。

思路：分别计算经过某节点的最长单边长度，然后用res记录遍历过程中的最大值。
拓展：求二叉树的最大路径和
思路：与前一题思路一样，需要注意的是，路径和是节点的和，节点和的值可能为负，因此在更新左右节点的和时，需要与0相比取最大值。

leetcode 判断树是否对称，即左右子树是否对称

思路：空树为对称，否则判断左右子树是否对称。

leetcode 求树中从上向下和为target的路径条数

思路：自我感觉这个题比较难，划分为easy有点不合适。思路为先看以根节点为路径开始节点的路径条数，然后分别对左右子树调用递归，计算以左右节点为路径开始节点的路径条数。这里，因为要对原始函数调用递归，所以要把统计路径条数的count写成类的成员变量，需要注意。

leetcode 二叉树的前序，中序，后序，层序遍历（递归与非递归实现，基础要求）

思路：前序；根，左，右 中序；左，根，右 后序；左，右，根
递归思路，按照各自的遍历顺序递归调用
非递归：利用栈存放遍历过程中的节点。后序遍历需要记录上一个遍历的节点，用于判断上个节点是否为当前节点的右孩子。
层序遍历：利用队列先进先出的思想，在入队时可以加上层数，构建pair对

leetcode 二叉搜索树中第k小的节点

思路：BST中序遍历的结果是有序的，因此可以用中序遍历找到第K个数返回。递归与非递归两种实现方式。另一种方法是写辅助函数，求左右子树的元素个数，然后二分，注意根节点也占一个位置。

leetcode 求能存储1-n的二叉树的数量

思路：这个是数学推导题，二叉树的数量为所有情况下左右子树数量的乘积和。可以用dp模拟递推式，求出最后解。

leetcode 抢劫房屋，要求抢劫的房子不能构成父子连线。

思路：辅助递归函数为从当前节点开始抢劫能获取的最大财富。那么可以取根节点+子子节点，子节点两者的最大值。这里注意函数参数为引用。

leetcode 二叉树转链表，链表顺序为前序遍历结果。

思路：转换过程中需要记录子树转换后的最后一个节点，便于与之前链表连接。转换顺序按照前序遍历顺序，先是根节点，然后左子树，最后右子树，也是用递归转换。

leetcode 依据前序和中序遍历结果构造二叉树

思路：先从前序中找到根节点，然后依据根节点从中序遍历中分开左右子树，递归构建左右子树。
拓展：依据后序和中序遍历结果构造二叉树
思路：

leetcode 二叉树中两节点的最小公共祖先

思路：方法一，利用回溯法寻找从根节点到两节点的路径，并记录下来，然后找到路径中最后一个相同的节点返回。方法二，利用原函数递归，分别对左右子树调用原函数，若两节点分别在左右子树中，则根节点为最小公共节点。否则为左右子树的其中一个节点。递归返回条件为根节点为空或者找到了任意一个节点。

leetcode 验证二叉树是否为二叉搜索树

思路：方法一，二叉搜索树的前序遍历结果为有序的，根据这个特性可以采用递归和非递归遍历，记录前一次遍历结果，与当前节点比较，若反序则返回。遍历顺序为左中右。方法二，二叉树左右子树节点要求小于或大于根节点，利用这个特性，构造辅助函数，将根节点的值分别作为最大值或最小值传入。

leetcode 序列化与反序列化二叉树

思路：方法一，递归遍历，利用前序遍历，根左右，依次将节点值记录在字符流中，空节点用“#”表示。方法二，非递归层序遍历，需要利用队列记录上一层的节点。