1.技巧描述

对于二叉树的问题，除了采用深度优先搜索和广度优先搜索外，还可以在这两个方法上做一些优化，比如建立辅助函数、用迭代代替递归、分情况讨论、预置标记变量。

  • 建立辅助函数：有时候一个大问题不好解决，但是先解决掉其中一个关键问题，后续就比较好办了。比如要判断A树中是否包含与B树完全相同的子树，可以先建立辅助函数，判断两棵子树是否完全相同，然后再遍历A树中所有的子树，依次进行判断即可。

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

  • 分情况讨论：一个复杂的问题可以拆分成多种情况来解决。比如求最近公共祖先。可以分四种情况，一是都在左子树，二是都在右子树，三是左子树、右子树各1个，四是左右子树都没有。

  • 预置标记变量：预置标记变量可用来判断是否是某种类型的树，或者判断某些节点是否被访问过。

2.实战演练

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

本题使用了迭代代替递归的技巧。通过栈来进行前序、中序和后序遍历。

本题使用了建立辅助函数的技巧。先判度两棵树是否相同，再递归遍历t1中所有的子树，并进行判断。

本题使用了深度优先搜索和广度优先搜索的方法。通过预置标记变量，来判断之前是否到达了叶子节点。

本题使用了分情况讨论的技巧。通过罗列所有的情况枚举出答案。