1.技巧描述

对于二叉树的问题，除了采用深度优先搜索和广度优先搜索外，还可以在这两个方法上做一些优化，比如预处理、用迭代代替递归、回溯。

  • 预处理：比如对要处理的数据提前做哈希映射，或者计算前缀和、后缀和，计算差分数组，构建前缀树，构建树状数组等等。

  • 用迭代代替递归：递归一般会有很多重复的计算过程，可以用迭代代替递归，从而提高效率。一般使用栈的方式来实现。

  • 回溯：通过特定的方式，回到上一层递归的状态。一般是删除集合最后一个元素，或者重置到原来的长度等等。

2.实战演练

本题使用了深度优先搜索的方法。对合并节点进行处理时，如果两者都不为空，新建一个节点，值为t1的值加上t2的值。

本题使用了预处理的技巧。通过对要处理的数据提前做哈希映射，从而快速找到根节点在中序序列的索引。

本题使用了深度优先搜索的方法。每次交换当前节点的左右子节点。

本题使用了迭代代替递归的技巧。通过栈来完成二叉树的中序遍历。

本题使用了回溯的技巧。通过删除集合的最后一个元素，从而回退到上一层节点的位置。