二叉树总结（四）

1.技巧描述

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

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

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

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

2.实战演练

• 合并二叉树

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

• 输出二叉树的右视图

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

• 二叉树的镜像

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

• 二叉树的中序遍历

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

• 二叉树根节点到叶子节点和为指定值的路径

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