二叉树总结
二叉树总结（一）
1.技巧描述
对于二叉树的问题，一般会采用深度优先搜索和广度优先搜索等方法来解决。
-
深度优先搜索：深度优先搜索会沿着某一条路一直往前走，直到走完这条路为止，有点类似不撞南墙不回头，一般使用递归来实现。
-
广度优先搜索：广度优先搜索会考虑所有可能的路径，每次往前走一步，都相当于在上一步的基础上进行扩展，一般采用队列的方式来实现。
2.实战演练
本题使用了深度优先搜索的方法。并通过回溯的方式，让路径回退到上一个节点，达到重置原路径的目的。
本题使用了深度优先搜索的方法。并通过定义贡献值的方式来找所有可能的最大路径和。
本题使用了深度优先搜索的方法。只要左子树或右子树不为空，则可以继续找路径。
本题使用了深度优先搜索的方法。左右子树深度的较大者加1即为当前子树深度
本题使用了广度优先搜索的方法。通过队列遍历树中所有的节点。
二叉树总结（二）
1.技巧描述
对于二叉树的问题，除了采用深度优先搜索和广度优先搜索外，还可以在这两个方法上做一些优化，比如剪枝、预处理、回溯。
-
剪枝：提前排除掉不合法的情况。
-
预处理：比如对要处理的数据提前做哈希映射，或者计算前缀和、后缀和等等。具体情况具体分析。
-
回溯：通过特定的方式，回到上一层递归的状态。一般是删除集合最后一个元素，或者重置到原来的长度等等。
2.实战演练
本题使用了剪枝的技巧。如果当前子树深度为-1，则直接作为不合法的情况排除掉。
本题使用了回溯的技巧。通过移除集合最后一个元素，回溯到上一层节点。
本题使用了预处理的技巧。通过建立中序序列的值与索引之间的映射，快速找到根节点在中序序列对应的索引。
本题使用了深度优先搜索的方法。
本题使用了广度优先搜索的方法。通过队列遍历树中所有的节点，并将偶数层反转，从而实现之字形顺序打印二叉树。
二叉树总结（三）
1.技巧描述
对于二叉树的问题，除了采用深度优先搜索和广度优先搜索外，还可以在这两个方法上做一些优化，比如建立辅助函数、用迭代代替递归、分情况讨论、预置标记变量。
-
建立辅助函数：有时候一个大问题不好解决，但是先解决掉其中一个关键问题，后续就比较好办了。比如要判断A树中是否包含与B树完全相同的子树，可以先建立辅助函数，判断两棵子树是否完全相同，然后再遍历A树中所有的子树，依次进行判断即可。
-
用迭代代替递归：递归一般会有很多重复的计算过程，可以用迭代代替递归，从而提高效率。一般使用栈的方式来实现。
-
分情况讨论：一个复杂的问题可以拆分成多种情况来解决。比如求最近公共祖先。可以分四种情况，一是都在左子树，二是都在右子树，三是左子树、右子树各1个，四是左右子树都没有。
-
预置标记变量：预置标记变量可用来判断是否是某种类型的树，或者判断某些节点是否被访问过。
2.实战演练
本题使用了广度优先搜索的方法。
本题使用了迭代代替递归的技巧。通过栈来进行前序、中序和后序遍历。
本题使用了建立辅助函数的技巧。先判度两棵树是否相同，再递归遍历t1中所有的子树，并进行判断。
本题使用了深度优先搜索和广度优先搜索的方法。通过预置标记变量，来判断之前是否到达了叶子节点。
本题使用了分情况讨论的技巧。通过罗列所有的情况枚举出答案。
二叉树总结（四）
1.技巧描述
对于二叉树的问题，除了采用深度优先搜索和广度优先搜索外，还可以在这两个方法上做一些优化，比如预处理、用迭代代替递归、回溯。
-
预处理：比如对要处理的数据提前做哈希映射，或者计算前缀和、后缀和，计算差分数组，构建前缀树，构建树状数组等等。
-
用迭代代替递归：递归一般会有很多重复的计算过程，可以用迭代代替递归，从而提高效率。一般使用栈的方式来实现。
-
回溯：通过特定的方式，回到上一层递归的状态。一般是删除集合最后一个元素，或者重置到原来的长度等等。
2.实战演练
本题使用了深度优先搜索的方法。对合并节点进行处理时，如果两者都不为空，新建一个节点，值为t1的值加上t2的值。
本题使用了预处理的技巧。通过对要处理的数据提前做哈希映射，从而快速找到根节点在中序序列的索引。
本题使用了深度优先搜索的方法。每次交换当前节点的左右子节点。
本题使用了迭代代替递归的技巧。通过栈来完成二叉树的中序遍历。
本题使用了回溯的技巧。通过删除集合的最后一个元素，从而回退到上一层节点的位置。
牛客题解
投递华为等公司10个岗位 >