平衡二叉树判断

  1. 题目描述
    1. 思路

题目描述

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

思路

  • 利用二叉树长度求法,递归求解(后序遍历)
  • 递归判断是否满足平衡二叉树的条件,左右子树的深度相差 <= 1
  • 后序遍历的应用
// 输入一棵二叉树,判断该二叉树是否是平衡二叉树。

// 利用求树的深度算法实现
class Solution {
public:
    //  递归求pRoot的深度
    int TreeDepth(TreeNode* pRoot)
    {
        if (pRoot == nullptr) {
            return 0;
        }
        
        int left = TreeDepth(pRoot->left) + 1;
        int right = TreeDepth(pRoot->right) + 1;
        
        return right > left ? right:left;
    }
    // 递归判断是否为平衡二叉树
    bool IsBalanced_Solution(TreeNode* pRoot) {
        if (pRoot == nullptr) {
            return true;
        }
        
        int left = TreeDepth(pRoot->left) + 1;
        int right = TreeDepth(pRoot->right) + 1;
        // 平衡判断
        int diff = left - right;
        if (diff > 1 || diff < -1) {
            return false;
        }
        
        return IsBalanced_Solution(pRoot->left) &&
            IsBalanced_Solution(pRoot->right);
    }
};

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 1056615746@qq.com

文章标题:平衡二叉树判断

字数:225

本文作者:攀登

发布时间:2019-12-26, 23:12:31

最后更新:2024-06-15, 15:53:35

原始链接:http://jiafeimao-gjf.github.io/2019/12/26/sword-%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91%E5%88%A4%E6%96%AD/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

×

喜欢就点赞,疼爱就打赏