MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » 二叉树平衡稽查(递归思想分析)

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

www.MyException.Cn  网友分享于:2013-08-22  浏览:0次
二叉树平衡检查(递归思想分析)

二叉树平衡检查

题目描述

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

解题思路

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

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

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

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

源代码

/*
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♪(・ω・)ノ

文章评论

Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
漫画:程序员的工作
漫画:程序员的工作
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
中美印日四国程序员比较
中美印日四国程序员比较
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
代码女神横空出世
代码女神横空出世
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
为什么程序员都是夜猫子
为什么程序员都是夜猫子
 程序员的样子
程序员的样子
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
程序员和编码员之间的区别
程序员和编码员之间的区别
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
编程语言是女人
编程语言是女人
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
每天工作4小时的程序员
每天工作4小时的程序员
旅行,写作,编程
旅行,写作,编程
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
10个调试和排错的小建议
10个调试和排错的小建议
程序员都该阅读的书
程序员都该阅读的书
鲜为人知的编程真相
鲜为人知的编程真相
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
我的丈夫是个程序员
我的丈夫是个程序员
那些争议最大的编程观点
那些争议最大的编程观点
如何成为一名黑客
如何成为一名黑客
总结2014中国互联网十大段子
总结2014中国互联网十大段子
老程序员的下场
老程序员的下场
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
一个程序员的时间管理
一个程序员的时间管理
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
我是如何打败拖延症的
我是如何打败拖延症的
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有