剑指Offer（三十九）：平衡二叉树

2018年1月16日17:40:32 15 4,934 °C
摘要

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

剑指Offer（三十九）：平衡二叉树

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

1、思路

平衡二叉树的定义是：所谓的平衡之意，就是树中任意一个结点下左右两个子树的高度差不超过 1。

解题思路有两种，只遍历一次的方法最优。

重复遍历多次：

在遍历树的每个结点的时候，调用函数TreeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过1，则这是一颗平衡的二叉树。这种方法的缺点是，首先判断根结点是不是平衡的，需要使用TreeDepth获得左右子树的深度，然后还需要继续判断子树是不是平衡的，还是需要使用TreeDepth获得子树的左右子树的深度，这样就导致了大量的重复遍历。

只遍历一次：

重复遍历会影响算法的性能，所以很有必要掌握不需要重复遍历的方法。如果我们用后序遍历的方式遍历二叉树的每一个结点，在遍历到一个结点之前我们就已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度（某一结点的深度等于它到叶结点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡的。

2、代码

C++：

重复遍历多次：

C++
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
class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if(pRoot == NULL){
            return true;
        }
        int left = TreeDepth(pRoot->left);
        int right = TreeDepth(pRoot->right);
        int diff = left - right;
        if(diff > 1 || diff < -1){
            return false;
        }
        return IsBalanced_Solution(pRoot->right) && IsBalanced_Solution(pRoot->left);
    }
private:
    int TreeDepth(TreeNode* pRoot)
    {
        if(pRoot == NULL){
            return 0;
        }
        int left = TreeDepth(pRoot->left);
        int right = TreeDepth(pRoot->right);
        return (left > right) ? (left + 1) : (right + 1);
    }
};

只遍历一次：

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int depth = 0;
        return IsBalanced(pRoot, &depth);
    }
private:
    int IsBalanced(TreeNode* pRoot, int* depth){
        if(pRoot == NULL){
            *depth = 0;
            return true;
        }
        int left, right;
        if(IsBalanced(pRoot->left, &left) && IsBalanced(pRoot->right, &right)){
            int diff = left - right;
            if(diff <= 1 && diff >= -1){
                *depth = 1 + (left > right ? left : right);
                return true;
            }
        }
        return false;
    }
};

感谢@小小毛提供的本地测试用例：

Python
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
31
32
33
34
35
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
 
class Solution:
    def TreeDepth(self, root):
        # write code here
        if root is None:
            return 0
        left = self.TreeDepth(root.left)
        right = self.TreeDepth(root.right)
        
        if abs(left-right)>1:
            return False
        return max(left,right)+1
 
if __name__=='__main__':
    A1 = TreeNode(1)
    A2 = TreeNode(2)
    A3 = TreeNode(3)
    A4 = TreeNode(4)
    A5 = TreeNode(5)
    A6 = TreeNode(6)
 
    A1.left=A2
    A1.right=A3
    A2.left=A4
    A2.right=A5
    A4.left=A6
 
    solution=Solution()
    ans=solution.TreeDepth(A1)
    print('ans=',ans)

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：15   其中：访客  8   博主  7

    • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3
      回复 2019年4月11日 上午10:34  沙发

      就是多了一步判断
      class TreeNode:
      def __init__(self, x):
      self.val = x
      self.left = None
      self.right = None

      class Solution:
      def TreeDepth(self, root):
      # write code here
      if root is None:
      return 0
      left = self.TreeDepth(root.left)
      right = self.TreeDepth(root.right)

      if abs(left-right)>1:
      return False
      return max(left,right)+1

      if __name__==’__main__’:
      A1 = TreeNode(1)
      A2 = TreeNode(2)
      A3 = TreeNode(3)
      A4 = TreeNode(4)
      A5 = TreeNode(5)
      A6 = TreeNode(6)

      A1.left=A2
      A1.right=A3
      A2.left=A4
      A2.right=A5
      A4.left=A6

      solution=Solution()
      ans=solution.TreeDepth(A1)
      print(‘ans=’,ans)

      • avatar Jack Ma 来自天朝的朋友 谷歌浏览器 Windows 7 上海市浦东新区 电信 0
        回复 2019年4月22日 上午12:41  板凳

        您好，python的实现第二个if那里好像出了点问题

          • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点
            回复 2019年4月22日 上午10:05  1层

            @Jack Ma 已更正~感谢

          • avatar 巨菜 来自天朝的朋友 谷歌浏览器 Windows 10 福建省厦门市 电信 0
            回复 2019年4月28日 下午6:20  地板

            python的代码牛客上跑不通。。

              • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点
                回复 2019年4月28日 下午6:40  1层

                @巨菜 测试了，确实没有acc。这是小毛毛提供的代码，当时没有测试。
                可以参考c++的思路写一个。

              • avatar Joey 谷歌浏览器 Mac OS X 10_14_4 亚太地区 1
                回复 2019年4月30日 上午8:37  4楼

                您好，我想问一下平衡二叉树不应该先满足二叉搜索树的条件么，为什么这道题不用判断左子树所有结点小于根结点小于右子树所有结点？

                  • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点
                    回复 2019年4月30日 上午9:51  1层

                    @Joey 不用满足，看下这个吧：
                    https://www.cnblogs.com/jielongAI/p/9565776.html

                      • avatar Joey 谷歌浏览器 Mac OS X 10_14_4 亚太地区 1
                        回复 2019年4月30日 上午11:57  2层

                        @Jack Cui 如果平衡二叉树说的就是AVL tree的话，那他应该先满足二叉搜索树的条件吧。链接里的图例也是默认满足的

                          • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点
                            回复 2019年4月30日 下午12:18  3层

                            @Joey 哦哦，贴的链接有问题，可以看下leetcode样例：
                            https://www.cnblogs.com/grandyang/p/4045660.html
                            样例没有满足搜索树的条件。
                            AVL tree应该是平衡二叉搜索树，这里是平衡二叉树，虽然也有混着叫的。
                            这里的考点应该只是是否平衡。

                              • avatar Joey 谷歌浏览器 Mac OS X 10_14_4 亚太地区 1
                                2019年4月30日 下午6:36  4层

                                @Jack Cui 哦哦，我一直以为他两是一个东西 :???:

                              • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市昌平区 联通
                                回复 2019年5月2日 上午11:04  3层

                                @Joey 看示例吧，根据情况分析。感觉很多时候都是叫成一个。

                          • avatar hello 来自天朝的朋友 谷歌浏览器 Linux 上海交通大学 汽车工程研究院 1
                            回复 2019年5月30日 下午2:55  5楼

                            class Solution:
                            def IsBalanced_Solution(self, pRoot):
                            # write code here
                            return self._IsBalanced_Solution(pRoot)[0]

                            def _IsBalanced_Solution(self, pRoot):
                            # write code here
                            if not pRoot:
                            return True, 0
                            flag1, left = self._IsBalanced_Solution(pRoot.left)
                            flag2, right = self._IsBalanced_Solution(pRoot.right)
                            return flag1 and flag2 and abs(left-right) 1:
                            return False
                            相当于直接把该遍历节点变成深度为0的空节点了,和 return 0 一样的效果,所以有问题吧

                              • avatar hello 来自天朝的朋友 谷歌浏览器 Linux 上海交通大学 汽车工程研究院 1
                                回复 2019年5月30日 下午2:57  1层

                                @hello 这评论少了好多内容23333

                                  • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点
                                    回复 2019年5月30日 下午7:18  2层

                                    @hello 嗯，这个python代码确实有问题 :arrow: :arrow: