【剑指Offer】平衡二叉树解题报告（Python & C++）

作者：负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/

题目描述

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

解题方法

平衡二叉树的定义是任何节点的左右子树高度差都不超过1的二叉树。

按照定义，很容易得出获得左右子树高度，然后判断。递归写法。

Python代码：

# -*- coding:utf-8 -*-

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    def IsBalanced_Solution(self, pRoot):

        if not pRoot: return True

        left = self.TreeDepth(pRoot.left)

        right = self.TreeDepth(pRoot.right)

        if abs(left - right) > 1:

            return False

        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)

    def TreeDepth(self, pRoot):

        if not pRoot: return 0

        left = self.TreeDepth(pRoot.left)

        right = self.TreeDepth(pRoot.right)

        return max(left, right) + 1

C++代码如下：

class Solution {

public:

    bool IsBalanced_Solution(TreeNode* pRoot) {

        if (!pRoot) return true;

        int left = depth(pRoot->left);

        int right = depth(pRoot->right);

        return abs(left - right) <= 1 && IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);

    }

    int depth(TreeNode* pRoot) {

        if (!pRoot) return 0;

        return max(depth(pRoot->left), depth(pRoot->right)) + 1;

    }

};

日期

2018 年 3 月 25 日 —— 周日，天气突然变热了。好风光好天气
2019 年 3 月 7 日 —— 3月开始，春天到了

巴特西

【剑指Offer】平衡二叉树解题报告（Python & C++）

目录

题目描述

解题方法

日期

最新文章

热门文章

巴特西

【剑指Offer】平衡二叉树 解题报告（Python & C++）

目录

题目描述

解题方法

日期

最新文章

热门文章

【剑指Offer】平衡二叉树解题报告（Python & C++）