二叉树总结（一）

1.技巧描述

对于二叉树的问题，一般会采用深度优先搜索和广度优先搜索等方法来解决。

  • 深度优先搜索：深度优先搜索会沿着某一条路一直往前走，直到走完这条路为止，有点类似不撞南墙不回头，一般使用递归来实现。

  • 广度优先搜索：广度优先搜索会考虑所有可能的路径，每次往前走一步，都相当于在上一步的基础上进行扩展，一般采用队列的方式来实现。

2.实战演练

本题使用了深度优先搜索的方法。并通过回溯的方式，让路径回退到上一个节点，达到重置原路径的目的。

本题使用了深度优先搜索的方法。并通过定义贡献值的方式来找所有可能的最大路径和。

本题使用了深度优先搜索的方法。只要左子树或右子树不为空，则可以继续找路径。

本题使用了深度优先搜索的方法。左右子树深度的较大者加1即为当前子树深度

本题使用了广度优先搜索的方法。通过队列遍历树中所有的节点。

二叉树总结（二）

1.技巧描述

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

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

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

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

2.实战演练

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

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

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

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

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

二叉树总结（三）

1.技巧描述

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

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

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

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

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

2.实战演练

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

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

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

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

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

二叉树总结（四）

1.技巧描述

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

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

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

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

2.实战演练

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

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

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

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

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