树形算法题的思考

树形是一大题型，这类题目相对来说比较简单，在我看来掌握树形的最大要点就是递归的思想，这可以说用在了这类题目中的方方面面。主要涉及这些题型：

  • 构建树（数组，链表）
  • 遍历，判断是合理的树
  • 找节点（LCA）
  • 树的基本属性（高度），找路径

构建树

这类题目的基本思路就是先找到根结点（root），然后把整个数组或者链表分成左右两个部分。之后，这个根节点的左子树就是递归调用数组的右半部分。右半边子树就是递归调用，这个函数的右半部分。总体还是比较简单的，题目可以参看

这里有一道题，关于如何利用链表来构造。其中有一点，它可以使用一个固定的prev linked list node。在每次递归结束的时候都会调用next，这样我们就不需要每次遍历找到中心结点，而是利用之前的结果来找到中间的那个节点。也就是说，在这里我们并不需要一开始就把父节点找到，而是可以先存好左子树，之后再到root。

	private ListNode list;
    private TreeNode sortedListToBST(int start, int end) {
        if (start > end) return null;
        int mid = (start + end+1) / 2;
        TreeNode leftChild = sortedListToBST(start, mid-1);
        TreeNode parent = new TreeNode(list.val);
        parent.left = leftChild;
        list = list.next;
        parent.right = sortedListToBST(mid+1, end);
        return parent;
}

其他的一些，比如说利用前序遍历和中序遍历来构建。思路是差不多的，因为我们可以知道，前序遍历的第一个必定是根节点，而中续遍历的中间某一个必定是根节点，然后，根据这个就可以确定左右子树的范围，之后递归调用就可以了。

序列化反序列化树的做法很多，我的做法是当出现null的时候写X, 对于n节点的就在最后一个子节点后面加X。

遍历

在刷题中，比较常见的题目就是通过一层一层，来遍历树，还有那种垂直遍历树。这种思路基本上差不多的，基本上都是BFS。每次遍历完一层之后，记住队列中的大小，然后遍历所有队列中的节点，再将下一行的内容都加到队列里，这样就可以实现一层一层的便利。如果需要翻过来输出，只需要每次加在开头就可以了。

如果需要垂直输出的话，我们只需要建立一个HashMap<Integer, List>，然后往里面根据列来放节点，列的获得是根据上一个节点，他左节点的话列-1，右节点，列数+1。我们还需要放这个节点与它的列数的对应。

其他的遍历方法还可以使用stack来进行遍历，将root的左节点放到放到stack里，一直到最左边，之后可以看栈顶的节点是否有用右节点，如果有的话，将这个pop出来之后，再一直从右节点开始遍历，直到最左边。这样就可以完成一个先序的遍历方法。

还有一些其他的题目，比如把二叉树变成链表，找到左子树的最右边，把右子树接上，然后就可以把左子树放到右边，删掉左子树。这个思路比较奇特，也可以使用递归的思路，把左右都flat好了之后就可以按上面的做法了。还有就是把树颠倒,就是一直到左，然后把父节点的右节点作为左节点，父节点是右节点。

另外一大类就是判断这个数是否符合条件，比如说是否相等，是否对称等的关系。这些也都是使用递归的思路就可以解决。比如说判断相等，只要判断根节点是否相等，然后再来判断左右子树是否相等，如果都是的话，那么就是true，要不然就是false。判断是否对称就是看左子树是否和右子树相等。还有一道类似的题目就是交换二叉树，方法就是把左子树先交换，然后再交换右子树，然后把两个颠倒就可以了。你也可以先存好一个节点，类似在数组中交换位置。

找节点

这种题目最经典的就是找公共最低祖先。方法就是看左子树和右子树有没有，如果没有的话那就返回null，如果其中有一个不是null的话就返回那个节点，如果两个节点都有的话，那么就返回根节点。如果是BST的话，可以直接根据节点的大小来判断位置。

还有就是根据这大小来在二叉搜索树中，找最近节点的题目，这个题目还是非常简单的，只要存一个目前的节点，每次和之前存的和target的比较，如果小的话就把它存好，之后就看着当前的值和它的大小，如果比较大的话就走左边，小的话就走右子树。

如果要存k个的话，先走左边，需要利用一个list来存，当list大小为k时，如果发现root的比list第一个更接近，就把第一个删掉，把root加进去。然后走右边。其实就是一个inorder的遍历，只不过加一个提前终止条件。每次发现新的比较接近就把最前面的扔掉

树的基本属性，找路径

这两种类型解法基本是相同的，如果是纯列出所有路径的题目，那么可以直接使用dfs+backtrack解决。如果是需要计算路径sum之类的话，那么就可以按照计算height的套路。

计算height的套路就是看左边的长度和右边的长度，之后选个最大的+1. 如果是计算diameter，就是左右相加以及+1。其他一些题对路径有一定的限定，可以在遍历时加上一个参数记录此时的值。

binary index tree

update

while j <= self.n:
    self.bit[j] += diff
    j += (j & -j)

query

while j:
    res+=self.bit[j]
    j-=(j&-j)

other