平衡二叉树

---

题目描述

输入一颗二叉树，判断该二叉树是否是平衡二叉树。 注意：在这里，只考虑其平衡性，不需要考虑其是不是排序二叉树，即不用考虑，左结点 < 根结点 < 右结点。

解题思路

平衡二叉树，即左右子树的深度相差不超过 1，并且其左右子树也必须是平衡二叉树。

有两种方法来解决这个问题：

• 第一种，从根结点开始，遍历每个结点的同时通过二叉树深度来判断其左右子树是否满足平衡二叉树的条件，这样依次遍历的坏处就是，从上到下的过程中存在大量的重复操作。
• 第二种，和后序遍历一样，从下到上开始，先遍历左右结点再遍历根结点，这样在遍历的过程中通过记录深度就判断了左右子树是否为平衡二叉树，减少了很多重复的遍历操作。

代码

第一种，全遍历的方法

class Solution
{
public:
    bool IsBalanced_Solution(TreeNode* pRoot)
    {
        if (pRoot == NULL)
            return true;
        
        int left = GetDepth(pRoot->left);
        int right = GetDepth(pRoot->right);
        
        if (abs(left - right) < 2)
            return true;
        
        return false;
    }
    
    int GetDepth (TreeNode* pRoot)
    {
        if (pRoot == NULL)
            return 0;
        
        int left = GetDepth(pRoot->left);
        int right = GerDepth(pRoot->right);
        
        return (left > right) ? (left + 1) : (right + 1);
    }
};

第二种方法，只遍历一次。

class Solution
{
public:
    bool IsBalanced_Solution(TreeNode* pRoot)
    {
        int depth = 0;
        return IsBalanced(pRoot, &depth);
    }
    
    bool 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 dif = left - right;
            if (abs(dif) < 2) // 左右深度差不大于 1
            {
                *depth = 1 + (left > right ? left : right);
                return true;
            }
           
        }
        return false;
    }
};

参考博文链接：https://cuijiahua.com/blog/2018/01/basis_39.html