1.技巧描述

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

  • 剪枝：提前排除掉不合法的情况。

  • 预处理：比如对要处理的数据提前做哈希映射，或者计算前缀和、后缀和等等。具体情况具体分析。

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

2.实战演练

本题使用了剪枝的技巧。如果当前子树深度为-1，则直接作为不合法的情况排除掉。

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

本题使用了预处理的技巧。通过建立中序序列的值与索引之间的映射，快速找到根节点在中序序列对应的索引。

本题使用了深度优先搜索的方法。

本题使用了广度优先搜索的方法。通过队列遍历树中所有的节点，并将偶数层反转，从而实现之字形顺序打印二叉树。