二叉树总结（一）

1.技巧描述

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

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

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

2.实战演练

• 二叉树根节点到叶子节点的所有路径和

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

• 二叉树中的最大路径和

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

• 二叉树中和为某一值的路径(一)

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

• 二叉树的最大深度

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

• 求二叉树的层序遍历

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