C語言平衡二叉樹真題練習(xí)

第C語言平衡二叉樹真題練習(xí)目錄一、題目描述二、解題思路自頂向下的遞歸（暴力解法）自底向上的遞歸（最優(yōu)解法）題目難度：簡單

LeetCode鏈接：平衡二叉樹

一、題目描述

給定一個二叉樹，判斷它是否是高度平衡的二叉樹。

本題中，一棵高度平衡二叉樹定義為：一個二叉樹每個節(jié)點的左右兩個子樹的高度差的絕對值不超過1。

二、解題思路

一棵二叉樹是平衡二叉樹，當(dāng)且僅當(dāng)其所有子樹也都是平衡二叉樹，因此我們使用遞歸的方式依次判斷其所有子樹是否為平衡二叉樹，就知道這棵二叉樹是不是平衡二叉樹了。

自頂向下的遞歸（暴力解法）

自頂向下類似于前序遍歷，先判斷當(dāng)前樹是否平衡，再判斷當(dāng)前樹的左右子樹是否平衡。

核心思路

寫兩個函數(shù)：

子函數(shù)：計算當(dāng)前任意一個節(jié)點(樹)root的高度root是空節(jié)點：Depth(root)=0root是非空節(jié)點：Depth(root)=max(Depth(root-left),Depth(root-right))+1

主函數(shù)：依次遞歸遍歷完root的所有子樹，對于「當(dāng)前遍歷到的子樹」，判斷是否平衡，首先計算其左右子樹的高度，然后判斷高度差是否不超過1

如果不超過，才能繼續(xù)往下遞歸遍歷「當(dāng)前樹的左右子樹」，判斷其是否平衡；如果超過1，說明不滿足平衡條件，則直接返回false，不用往下遞歸了。

遞歸過程演示：自頂向下的遞歸類似于前序遍歷

/**

*Definitionforabinarytreenode.

*structTreeNode{

*intval;

*structTreeNode*left;

*structTreeNode*right;

*};

//計算當(dāng)前任意一個節(jié)點(樹)的高度（子函數(shù)）

intTreeDepth(structTreeNode*root)

//當(dāng)前節(jié)點為空

if(root==NULL)

return0;

//當(dāng)前節(jié)點不為空，分別計算它的左右子樹的高度

intleftDepth=TreeDepth(root-left);

intrightDepth=TreeDepth(root-right);

//當(dāng)前節(jié)點(樹)的高度

returnleftDepthrightDepthleftDepth+1:rightDepth+1;

boolisBalanced(structTreeNode*root){

//依次遞歸遍歷完root的所有子樹，分別判斷當(dāng)前子樹是否為高度平衡二叉樹

//當(dāng)前樹的根節(jié)點為空，說明其滿足高度平衡的二叉樹，返回true

if(root==NULL)

returntrue;

//當(dāng)前樹的根節(jié)點不為空，分別計算它左右子樹的高度

intleftDepth=TreeDepth(root-left);

intrightDepth=TreeDepth(root-right);

//計算左右子樹的高度差

intret=leftDepthrightDepthleftDepth-rightDepth:rightDepth-leftDepth;

//高度差不超過1，才能繼續(xù)往下遞歸遍歷當(dāng)前樹的左右子樹

returnret=1isBalanced(root-left)isBalanced(root-right);

}

復(fù)雜度分析：

時間復(fù)雜度：O(n2)，其中n是二叉樹中的節(jié)點個數(shù)。

最壞情況下，二叉樹是滿二叉樹，主函數(shù)isBalanced(root)需要遍歷二叉樹中的所有節(jié)點，時間復(fù)雜度是O(n)。計算每個子樹的最大高度函數(shù)TreeDepth(root)被重復(fù)調(diào)用。除了根節(jié)點，其余所有節(jié)點都會被遍歷兩次，復(fù)雜度為O[2(n-1)]，所以時間復(fù)雜度為n*2(n-1)n2。

空間復(fù)雜度：O(n)，其中n是二叉樹中的節(jié)點個數(shù)?？臻g復(fù)雜度主要取決于遞歸調(diào)用的層數(shù)，遞歸調(diào)用的層數(shù)不會超過n。

自底向上的遞歸（最優(yōu)解法）

方法一自頂向下遞歸，類似前序遍歷，先判斷當(dāng)前樹是否平衡，再判斷當(dāng)前樹的左右子樹是否平衡，所以對于同一個節(jié)點，函數(shù)TreeDepth會被重復(fù)調(diào)用，會重復(fù)計算很多次子樹的高度，導(dǎo)致時間復(fù)雜度較高。

如果使用自底向上的做法，則對于每個節(jié)點，函數(shù)TreeDepth只會被調(diào)用一次。因為到達左子樹底部后，每次對應(yīng)的左子樹都是放在遞歸調(diào)度中的，每次只需要獲取新的右子樹長度便可。

自底向上遞歸類似于后序遍歷，對于當(dāng)前遍歷到的節(jié)點，先遞歸地判斷其左右子樹是否平衡，再判斷以當(dāng)前節(jié)點為根的子樹是否平衡。

如果當(dāng)前樹的左/右子樹中只要有一個不平衡，則整個樹就不平衡，返回-1（表示不平衡）如果當(dāng)前樹是平衡的，則返回其高度，否則返回-1（表示不平衡）。

寫遞歸算法需要關(guān)注什么？

整個遞歸的終止條件：遞歸應(yīng)該在什么時候結(jié)束？子樹根節(jié)點為空的時候，空樹也是平衡二叉樹。本級遞歸應(yīng)該做什么？判斷當(dāng)前樹的左子樹、右子樹、以及當(dāng)前樹是否是平衡的。返回值：應(yīng)該返回給上一級的返回值是什么？當(dāng)前樹是平衡的，則返回其高度，不平衡則返回-1。

遞歸算法流程：

每一級遞歸時，在我們眼中，當(dāng)前樹就是這樣的，只有root、left、right三個節(jié)點。

到葉子節(jié)點了，當(dāng)前樹根節(jié)點root為空，說明是平衡的，則返回高度0；

當(dāng)前樹根節(jié)點root不為空，計算左右子樹left和right的高度，并判斷：

如果「左子樹left高度為-1」、或「右子樹right高度為-1」、或「左右子樹高度差1」，說明整個樹不平衡，直接返回-1（表示不平衡）。如果不滿足上面3種情況，說明當(dāng)前樹是平衡的，返回當(dāng)前樹的高度，即max(left,right)+1。

補充：計算絕對值的函數(shù)：intabs(intn);，頭文件stdlib.hormath.h。

遞歸過程演示：自底向上遞歸類似于后序遍歷

/**

*Definitionforabinarytreenode.

*structTreeNode{

*intval;

*structTreeNode*left;

*structTreeNode*right;

*};

//計算當(dāng)前樹的高度，并判斷當(dāng)前樹是否是平衡二叉樹

int_isBalanced(structTreeNode*root)

//先分別判斷當(dāng)前樹的左/右子樹是否平衡

//如果當(dāng)前樹的左/右子樹中只要有一個不平衡，則全樹就不平衡，返回-1（表示不平衡）

//如果當(dāng)前樹的左右子樹都平衡，則繼續(xù)判斷當(dāng)前樹是否平衡

//1.到葉子節(jié)點了，當(dāng)前樹根節(jié)點為空，說明是平衡的，則返回高度0

if(root==NULL)

return0;

//2.當(dāng)前樹根節(jié)點不為空

//計算左右子樹的高度

intleftTreeDepth=_isBalanced(root-left);

intrightTreeDepth=_isBalanced(root-right);

//不平衡的3種情況：左子樹高度為-1，右子樹高度為-1，左右子樹高度差1

if(leftTreeDepth==-1||rightTreeDepth==-1||abs(leftTreeDepth-rightTreeDepth)1)

return-1;

//如果不滿足上面3種情況，說明當(dāng)前樹是平衡的，返回當(dāng)前樹的高度

returnleftTreeDepthrightTreeDepthleftTreeDepth+1:rightTreeDepth+1;

boolisBalanced(structTreeNode*root){

//遞歸遍歷過程中：

//只要有一個子樹高度為-1，說明整個樹是不平衡的，返回false

//所有子樹高度都不等于-1，說明整個樹是平衡的，返回true

return_isBalanced(root)!=-1