判断是否是平衡二叉树

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

我本来想的是用dfs，每个节点递归，然后回溯看右节点，但是发现不会写。这个递归还是没有理解好，dfs跟bfs也不熟练，这两个方法使用来遍历图的，图是树的特殊状态（个人观点），所以主要还是算法的本质掌握的不熟练。那这道题呢，有两个方法。

1.平衡二叉树是任意节点的左右子树深度相差不能为1的，所以我们可以计算每个节点的深度，来看这颗树是不是平衡的。

class Solution
{
public:
    bool IsBalanced_Solution(TreeNode* pRoot)
    {
        if(!pRoot) return true;
        int left = getdepth(pRoot->left);
        int right = getdepth(pRoot->right);
        if(abs(left-right)>1)
            return false;
        return(IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right));
    }

    //递归实现，dfs
    int getdepth(TreeNode* pRoot)
    {
        if(!pRoot) return 0;
        int left = getdepth(pRoot->left);
        int right = getdepth(pRoot->right);
        return max(left+1,right+1);
    }

    //迭代，bfs
    int getdepth(TreeNode* pRoot)
    {
        if(!pRoot)  return 0;
        queue<TreeNode*> que;
        que.push(pRoot);
        int depth =0;
        while(!que.empty())
        {
            int size = que.size();
            ++depth;
            for(int i=0;i<que.size();++i)
            {
                TreeNode* temp = que.front();
                que.pop();
                if(temp->left)
                    que.push(temp->left);
                if(temp->right)
                    que.push(temp->right);
            }
        }
        return depth;
    }
}

那么这个呢是根据每个节点的深度来判断这棵树是不是平衡二插树。算深度的算法使用了迭代和递归两种方法来实现。这个算法有个问题就是，判断true／false只在is那个函数里面判断了，所以我们要每个节点都遍历，这样下层的节点实际上我们就走了很多次。这个是很浪费时间的。所以就有第二个算法。

2

class Solution
{
public:
    bool status = true;

    bool IsBalanced_Solution(TreeNode* pRoot)
    {
        getdepth(pRoot);
        return status;
    }

    int getdepth(TreeNode* pRoot)
    {
        if(!pRoot) return 0;
        int left=getdepth(pRoot->left);
        int right=getdepth(pRoot->right);
        if(abs(left-right)>1)
            status = false;
        return max(left+1,right+1);
    }

}

这个方法看上去跟上一个类似，但是还有区别的。上一个只在is函数里面才有false／true，并且每个is函数都要调用一下getdepth函数。所以每个节点会计算很多啊遍。
而第二个方法在getdepth中有true和false，只要有一个节点不满足平衡就返回false，并且getdepth只计算了一次全部的节点，没有多余的计算。

以上。