【剑指Offer】（树）平衡二叉树

比眉伴天荒 2022-03-16 01:12 184阅读 0赞

**题目链接**：[https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11192&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking][https_www.nowcoder.com_practice_8b3b95850edb4115918ecebdf1b4d222_tpId_13_tqId_11192_tPage_2_rp_2_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]

#### 题目描述 ####

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

#### 解决方法1 ####

class Solution { 
    public:
        bool IsBalanced_Solution(TreeNode* pRoot) { 
            if(!pRoot) return true;
            return abs(TreeDepth(pRoot->left)-TreeDepth(pRoot->right))<=1 &&
                IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
        }
        
        int TreeDepth(TreeNode* pRoot)//求二叉树的深度
        { 
            if(!pRoot) return 0;
            return 1+max(TreeDepth(pRoot->left),TreeDepth(pRoot->right));
        
        }
    };

#### 解决方法2 ####

class Solution { 
    public:
        bool IsBalanced_Solution(TreeNode* pRoot) { 
            //这里只需判断是否节点深度相差都不超过1即可，无需判断是中序遍历是递增的
            if(!pRoot) return true;
            int depth=0;
            return IsBalanced(pRoot,&depth);
        }
        bool IsBalanced(TreeNode* p,int *depth){ //一边遍历一遍计算
            if(!p) { *depth=0; return true;}
            int left=0,right=0;
            if(IsBalanced(p->left,&left) && IsBalanced(p->right,&right)){ 
                int diff=abs(right-left);
                if(diff<=1){ *depth=1+max(left,right);return true;}
            }
            return false;
        }
    };

[https_www.nowcoder.com_practice_8b3b95850edb4115918ecebdf1b4d222_tpId_13_tqId_11192_tPage_2_rp_2_ru_ta_coding-interviews_qru_ta_coding-interviews_question-ranking]: https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11192&tPage=2&rp=2&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking