二叉树平衡检查(递归思想分析)

二叉树平衡检查

题目描述

实现一个函数,检查二叉树是否平衡,平衡的定义如下,对于树中任意一个结点,两颗子树的高度差不超过1。
给定指向树根结点的指针TreeNode* root,请返回一个bool,代表这棵树是否平衡。

解题思路

树结构自身就是递归定义,很多问题都可以利用递归巧妙地实现,对于这道题,关键点有两处:

  1. 求结点左右子树高度差
  2. 遍历树中所有结点

之前我们做过树的最大深度问题以及树的遍历问题,将两者结合起来,便可以解决这两个关键点。
解题思路为:

  1. 若根结点为空,则二叉树平衡
  2. 调用Depth函数求结点高度
  3. 分别求出结点左右子树高度并将高度差赋给differ,判断是否满足平衡二叉树的条件
  4. 递归遍历左子树和右子树,重复以上操作

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/

class Balance {
public:
bool isBalance(TreeNode* root) {
if (!root)
return true;
int differ=Depth(root->left)-Depth(root->right);
if (differ>1||differ<-1)
return false;
return isBalance(root->left)&& isBalance(root->right); //递归遍历树中所有结点
}
//计算结点高度
int Depth(TreeNode *root) {
if (!root)
return 0;
int L_high=Depth(root->left);
int R_high=Depth(root->right);
return (left>right) ? (left+1) : (right+1);
}
};

递归思想分析

这道题中值得一提的是其中体现出的递归思想源代码中有两处递归调用,而如果我们去观察的话,会发现它们的形式是不同的。isBalance函数中,问题的解决递归调用函数之前,而在Depth函数中,递归调用函数问题的解决之前。但是,这又有什么不同呢?

我们知道递归是一个调用并返回的过程,它要求待解决的问题可以拆分为很多个解法相同或类似的小问题,通过的过程由近及远,到达临界点(也就是结束条件)然后再开始,我们经常搞不清楚的是在这样一个过程中,问题是如何一步步被解决的?

之前看了一篇关于大脑理解递归的文章,里面对于这一点讲得很好,对于我理解递归起到了很大的帮助。
递归过程有不同的模式,而它们都有三个共同的要素:递+结束条件+归

模式1

function(大问题)  {
    if (end_condition)  {             //结束条件
        return ;
    }
    else  {
        //先将一个大问题拆分为小问题,当“递”到“结束条件”返回的过程中,再依次解决问题
        recursive(小问题);          // 递  =>  递归调用函数
        solve questions;           // 归  =>  问题的解决
    }
}

这种模式就对应于源代码中的Depth函数,假如我们给定一棵如下结构的二叉树,


我们去分析Depth函数的递归流程,如下:


从图中可以看出,程序的执行流程是递归调用函数(递)→返回(结束条件)→解决问题(归),问题是在递归调用返回的过程中一步步被解决的。

模式2

function(大问题)  {
    if (end_condition)  {          //结束条件
        return ;
    }
    else  {
        //在将大问题逐步拆分为小问题的同时去解决问题
        solve questions;            // 递  => 问题的解决
        recursive(小问题);          // 递  => 递归调用函数
    }
}

这种模式就对应于源代码中的isBalance函数,依旧利用上面提及的二叉树结构,去分析isBalance函数的递归流程,如下:


从图中可以看出,程序的执行流程是解决问题(递)→递归调用函数(递)→返回(结束条件)→一步步返回上层(归),每一次问题的解决都是在递归调用函数的过程中()便已经被解决,而不是在返回()的过程中。

对于递归思想的理解,有人曾做了一个形象的比喻:

你打开面前这扇门,看到屋里面还有一扇门(这门可能跟前面打开的门一样大小(静),也可能门小了些(动)),你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,你继续打开,。。。, 若干次之后,你打开面前一扇门,发现只有一间屋子,没有门了。 你开始原路返回,每走回一间屋子,你数一次,走到入口的时候,你可以回答出你到底用这钥匙开了几扇门。

这种说法其实并不全面,它对应了模式1,在的过程中一步步解决问题。
而我们可以对其稍加修改,这样就可以对应模式2

你打开面前这扇门,看到屋里面还有一扇门(这门可能跟前面打开的门一样大小(静),也可能门小了些(动)),你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,你继续打开。。。而在打开门的过程中,每走到一间屋子,你数一次, 若干次之后,你打开面前一扇门,发现只有一间屋子,没有门了。 你开始原路返回,走到入口的时候,你可以回答出你到底用这钥匙开了几扇门。

这两种形式都有调用并返回(递归)的过程,不同点在于问题被解决的时机不同,有可能是在的过程中就已经被解决,也可能是在的过程中被解决。

以上是我对于递归的一些理解,可能会有不当之处,望指出Thanks♪(・ω・)ノ

-------------The End-------------