今天來學習一下，給定一顆二叉樹，如何判斷這個二叉樹是否為平衡二叉樹。

不平衡二叉樹

給出如上二叉樹，它是不平衡的，輸出 false。

現在的二叉樹的TreeNode如下：

二叉樹的節點

所以這個問題，最直觀的想法就是，寫一個求高度的函式。求高度函式可以使用遞迴法，樹的高度等於左右子樹的高度的最大值再加1，加1的原因是自身節點本身的高度為1。遞迴二叉樹的高度程式碼如下：

計算二叉樹節點高度

有了節點高度之後，我們先看一下普通的解決思路：

判斷根結點是否為二叉平衡樹（求出左右子樹的高度，判斷它們的高度差是否超過了1）。遞迴判斷根的左子樹是否為平衡二叉樹遞迴判斷根的右子樹是否為平衡二叉樹

這裡需要說明的是，空樹也是平衡二叉樹。

bool IsBlanced_selector(BTreeNode pRoot) {	if(!pRoot)return true;//空樹也是平衡二叉樹    //計算根節點高度差，求出左右子樹的高度    int pf = getTheHigh(pRoot->_left) - getTheHigh(pRoot->_right);               if(pf >= -1 && pf <= 1)  //高度差絕對值小於1，再看它的左右子樹是否為二叉平衡樹       //遞迴其左右子樹        return IsBlanced_selector(pRoot->_left) && IsBlanced_selector(pRoot->_right);             return false;   //高度差絕對值大於1，不是二叉平衡樹}

這種方法類似於二叉樹的先序遍歷，先序遍歷了根節點的PF，再先序遍歷左右子樹的PF。這樣的程式碼效率很低，存在著重複計算。從1開始求高度時，需要遍歷3,4,5；到3後，求高度時，還需要遍歷4,5；這就導致了重複計算。

既然這樣，我們換成後續遍歷不就可以了嗎？

首先，判斷它的左子樹是否為平衡二叉樹然後在判斷它的右子樹是否為平衡二叉樹判斷它們是否為平衡二叉樹的同時，記錄它們的左右子樹的深度最後在判斷以這個結點為根的樹是否為平衡二叉樹

//判斷樹是否為平衡二叉樹(true:是 false:不是)//最佳化版本(不用遍歷重複的結點)bool IsBlancedTree_op_selector(BTreeNode pRoot, int & pdepth){    if (pRoot == NULL)    {        pdepth = 0;        return true;    }    //按照後序遍歷去判斷,先判斷左右子樹，然後記錄以當前結點為根樹的深度    int left, right = 0;//記錄左節點和右節點深度	//採取傳引用的方式，下層遞迴進行對深度修改以後會影響上一層    if (IsBlancedTree_op_selector(pRoot->_left, left) && IsBlancedTree_op_selector(pRoot->_right, right))    {        int pf = right - left;//計算平衡因子        if (pf <= 1 && pf >= -1)//判斷平衡因子是否合法        {			//合法就讓自身加上子樹的深度，然後因為是傳引用，所以當遞歸回到上一層的時候，上層中的right和left就是左右子樹的深度            pdepth = left>right ? left + 1 : right + 1;            return true;        }    }    return false;}

這種方法計算下來，只對這棵樹進行了一遍後序遍歷，時間複雜度會大大下降。