二叉树和分治法

Outline:

• 二叉树的遍历

• 前序遍历非递归方法

• 前序遍历分治法

• 遍历方法与分治法

• Maximum Depth of Binary Tree

• Balanced Binary Tree

• 二叉树的最大路径和 (root->leaf)

• Binary Tree Maximum Path Sum II (root->any)

• Binary Tree Maximum Path Sum (any->any)

• 二叉查找树

• Validate Binary Search Tree

• Binary Search Tree Iterator

• 二叉树的宽度优先搜索

• Binary Tree Level-Order Traversal

---

1.二叉树的遍历

这个应该是二叉树里面最基本的题了，但是在面试过程中，不一定会考递归的方式，很有可能会让你写出非递归的方法，应该直接把非递归的方法背下来。这里我就不多说了，直接把中序遍历的非递归方法贴出来吧，最后再加入一个分治法。

非递归方法（C++）：

分治法（Java）：

这两种方法也是比较直观的，前一个比较基础，我就不详细叙述了，但是分治法是值得重点说一说的。前面的遍历的方法是需要对每一个点进行判断和处理的，根据DFS进入到每一个节点，然后操作；但是使用分治法的话，就不需要考虑那么多，分治法的核心思想就是把一个整体的问题分为多个子问题来考虑，也就是说：每一个子问题的操作方法都是一样的，子问题的解是可以合并为原问题的解的（这里就是和动态规划、贪心法不一样的地方）。

所以使用分治法的话，就不需要对每个节点都进行判断，不管左右子树的情况（是否存在），直接进行求解，最后把它们合并起来。之前听课的时候老师也说过分治法就像一个女王大人，处于root的位置，然后派了两位青蛙大臣去处理一些事物，女王大人只需要管好自己的val是多少，然后把两个大臣的反馈直接加起来就可以了。个人认为分治法算是比较接近普通人思维的一种方法了。

---

2. 遍历方法与分治法

遍历方法其实在我经过之前各种刷题套模板后算是能够熟悉掌握了，所谓“虽不知其内涵，但知其模板”的境界，今天这个总结，确实帮助不少。直接承接了上面所说的两种思考。接下来我就直接用题解来分析一下：

2.1 Maximum Depth of Binary Tree

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的距离。

样例

给出一棵如下的二叉树:

 1 / \ 2   3   / \  4   5

这个二叉树的最大深度为3




这个题目要是在面试的时候面到，那必须一分钟内写出来，因为如果考虑分治法的话，就是一个简单的DFS，代码如下（Java）：

就是递归查看左右两边最大的深度，然后返回就可以。这个思路也比较简单，我就不多说了。

接下来再来一个题目：

2.2 Balanced Binary Tree

给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是：一棵二叉树中每个节点的两个子树的深度相差不会超过1。 

样例

给出二叉树 A={3,9,20,#,#,15,7}, B={3,#,20,15,7}

A) 3 B) 3 / \ \ 9 20 20 / \ / \ 15 7 15 7

二叉树A是高度平衡的二叉树，但是B不是

这个题目思路也比较简单，判断一下左右子树的高度差是否小于1，也是一个简单的分治法问题。这里用一种比较高大上的方法，加入了一个ResultType类，代码如下(Java)：

这里的ResultType保存了一个布尔值判断子树是否是平衡二叉树，用一个最大深度表示该子树的最大深度。然后在Divide阶段，分别递归调用了左右子树，之后判断左右子数的最大深度差，并且判断它们是否满足平衡二叉树，最后返回该子树的最大深度。这个思考也是比较自然合理的。运用了这种调用类的方式来进行解答，颇有一番面向对象的感觉，但是本人是不太喜欢这种方式的，因为不容易思考，还需要考虑很多自己不熟悉的地方，容易出错。

接下来就是本篇文章的重要部分了。我要详细描述一下二叉树的最大路径这个问题，记得有一次面试还面到过这个题，我也要把不同的情况写出来。

先来最简单的部分吧，给一棵二叉树，找出从根节点出发到叶节点的路径中，和最大的一条。这个就比较简单了，直接遍历整个树，然后找到最大的路径即可，这里我就不多说了，比较简单。直接上题目吧：

2.3 （1）二叉树的最大路径和（root->leaf）

给一棵二叉树，找出从根节点出发到叶节点的路径中，和最大的一条。

样例

给出如下的二叉树：

 1 / \2   3

返回4。(最大的路径为1→3)

就不需要多解释了，我就直接把代码贴出来（Java）:

2.4 Binary Tree Maximum Path Sum II (root -> any node)

给一棵二叉树，找出从根节点出发的路径中，和最大的一条。

这条路径可以在任何二叉树中的节点结束，但是必须包含至少一个点（也就是根了）。

样例

给出如下的二叉树：

 1 / \2   3

返回4。(最大的路径为1→3)

这个就跟原始版的题目不一样了，这里是从根到任意的节点，当然就不能采用原始问题的方法了，不然就是指数级别的复杂度了，这里就采用分治法了：

我们把分治的基本思想考虑进去：

1.递归的出口：当节点为null

2.Divide：分别对左右进行递归

3.Conquer：把得到的结果进行操作。

代码如下(Java)：

这里有一个关键点，对于某一个节点来说，得到了左右子树的和，这里我就要判断是否加上子树（这个部分就是和原始问题不一样的地方，保证了是任意的节点），加上子树的话是加左子树还是右子树，然后就能得到最大值了。这个题最大的关键还是在于不考虑左右子树如何，就把他们派出去，得到结果以后再进行判断。

2.5 Binary Tree Maximum Path Sum (any node -> any node)

给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）

样例

给出一棵二叉树：

 　　 1      / \     2   3

返回 6

这个题是上一个题目的升级版，这里求的就是任意两个点的最大路径和了。这样的题其实就是从上面的题做了一个引申，不过之前的题必须考虑到root，所以就直接判断左右子树，而这里的话，就不需要考虑root了，所以问题就变成了一个“把每一个节点都当作root来考虑的问题”，这里是我自己的理解，可能我没有表达清楚，也就是说，在每一步递归中，都需要把当前的root考虑为上一题中的root，然后来判断哪个root得到的值是最大的。所以这里就需要增加一个全局变量来存储了。代码如下（C++）：

这个题关键就在于你要去判断左右子树的值是否会让这一个小团的值变小，如果会，那就不加上左右子树。最后的return也是一个关键的地方：因为不能有分叉，所以只返回一条路径。

这两个题目就是充分运用了分治的方法，还需要大家很深刻的去理解一下其中的内涵，还是有一些需要思考的地方。

---

3. 二叉查找树

个人认为在树的题目中，最令人开心的就是二叉查找树了，因为这种结构本身就带有一种光环：左子树小于root，右子树大于root，这方面的题只需要紧紧围绕这个概念来做就可以。

3.1 Validate Binary Search Tree

给定一个二叉树，判断它是否是合法的二叉查找树(BST)

一棵BST定义为：

• 节点的左子树中的值要严格小于该节点的值。

• 节点的右子树中的值要严格大于该节点的值。

• 左右子树也必须是二叉查找树。

• 一个节点的树也是二叉查找树。

样例

一个例子：

 2 / \1   4   / \  3   5

上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.

看了这道题，我的第一个想法就是，判断左边最大的是否小于root，然后判断右边最小的是否大于root，然后递归去判断。这个算法复杂度也比较高，可以贴上来给大家看看(C++)：

思路很简单，就是找到左边，然后找到最右的子树，然后判断root的val和它的关系，右子树同理。之后递归往下进行判断。

另一种方法就优化了很多，用一个全局变量来存储前一个指针，然后和当前的root比较，然后更新这个指针，代码如下（C++）：

这个方法比较直观，就是利用二叉树的中序遍历的方法，其中last每次都更新为当前的节点。

关于二叉查找树还有一个简单的设计类的题，我就不多说了，直接上题吧：

3.2 Binary Search Tree Iterator

Design an iterator over a binary search tree with the following rules:

• Elements are visited in ascending order (i.e. an in-order traversal)

• next() and hasNext() queries run in O(1) time in average.

Example

For the following binary search tree, in-order traversal by using iterator is [1, 6, 10, 11, 12]

  10 /    \1      11 \       \  6       12

我使用了队列的方式来存储二叉树，然后进行相应的操作，代码如下(C++):

---

4. 二叉树的宽度优先搜索

终于到了我最喜欢的环节，传说中的BFS，这个环节比较经典，因为基本都可以套模板，不同的题只要加入一些不同的小trick就可以做出来，比如拓扑排序、图遍历啊等等，都需要用到BFS。前段时间在做我的图像中像素的最大连通域的时候也用到了BFS，感觉比较常见，也相比于DFS的递归方法实现要容易思考。

4.1 Binary Tree Level-Order Traversal

给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问）

样例

给一棵二叉树 {3,9,20,#,#,15,7} ：

 3 / \9  20  /  \ 15   7

返回他的分层遍历结果：

[  [3],  [9,20],  [15,7]]

有一种方法是判断一下当前队列的size，然后以此作为分层的判断，之后进行size次循环，表示一层。代码如下(C++):

还有一种方法是在每层遍历完之后加入一个NULL指针作为分界的标准，当到达NULL的时候，判断q是否为空，不为空则表示当前层已经遍历结束，然后把当前层push_back到res中，然后清空；q为空则表示到达最后一层，记录答案然后返回即可。代码如下（C++）:

---

总结

本文对二叉树和分治法进行了一个阐述。这次好好总结一下觉得有很多地方需要用到分治。我把以前写的分治法的总结帖在下面吧：

一、概念

对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。

 

二、分治法适用情况

1）问题的规模缩小到一定程度就可以容易解决

2）具有最子结构的性质（递归思想）

3）子问题的解可以合并为原问题的解（关键，否则为贪心法或者动态规划法）

4）子问题是相互独立的 ，子问题之间不包含公共的子子问题（重复解公共的子问题，一般用动态规划法比较好）

三、分治法的步骤

step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题

step2 解决：子问题规模较小而容易被解决则直接解决，否则递归地解各个子问题

step3 合并：将各个子问题的解合并为原问题的解

 

设计模式

Divide-and-Conquer(P)

     if |P|<=n0 then="" return="">

     将P分解为较小的字问题P1,P2,…,Pk

     for i<-1 to="">

          do Yi <- divide-and-conquer(pi)="">

     T <- merge(y1,y2,…,yk)="">

     return (T)