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

LeetCode鏈接：平衡二叉樹

一、題目描述

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

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

二、解題思路

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

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

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

核心思路

寫兩個(gè)函數(shù)：

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

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

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

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

/**

*Definitionforabinarytreenode.

*structTreeNode{

*intval;

*structTreeNode*left;

*structTreeNode*right;

*};

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

intTreeDepth(structTreeNode*root)

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

if(root==NULL)

return0;

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

intleftDepth=TreeDepth(root-left);

intrightDepth=TreeDepth(root-right);

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

returnleftDepthrightDepthleftDepth+1:rightDepth+1;

boolisBalanced(structTreeNode*root){

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

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

if(root==NULL)

returntrue;

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

intleftDepth=TreeDepth(root-left);

intrightDepth=TreeDepth(root-right);

//計(jì)算左右子樹的高度差

intret=leftDepthrightDepthleftDepth-rightDepth:rightDepth-leftDepth;

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

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

}

復(fù)雜度分析：

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

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

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

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

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

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

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

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

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

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

遞歸算法流程：

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

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

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

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

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

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

/**

*Definitionforabinarytreenode.

*structTreeNode{

*intval;

*structTreeNode*left;

*structTreeNode*right;

*};

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

int_isBalanced(structTreeNode*root)

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

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

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

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

if(root==NULL)

return0;

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

//計(jì)算左右子樹的高度

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){

//遞歸遍歷過程中：

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

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

return_isBalanced(root)!=-1