C語言平衡二叉樹真題練習(xí)
題目難度:簡單
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,不用往下遞歸了。
遞歸過程演示:自頂向下的遞歸類似于前序遍歷
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ // 計算當(dāng)前任意一個節(jié)點(樹)的高度(子函數(shù)) int TreeDepth(struct TreeNode* root) { // 當(dāng)前節(jié)點為空 if(root == NULL) { return 0; } // 當(dāng)前節(jié)點不為空,分別計算它的左右子樹的高度 int leftDepth = TreeDepth(root->left); int rightDepth = TreeDepth(root->right); // 當(dāng)前節(jié)點(樹)的高度 return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; } bool isBalanced(struct TreeNode* root){ // 依次遞歸遍歷完root的所有子樹,分別判斷當(dāng)前子樹是否為高度平衡二叉樹 // 當(dāng)前樹的根節(jié)點為空,說明其滿足高度平衡的二叉樹,返回true if(root == NULL) { return true; } // 當(dāng)前樹的根節(jié)點不為空,分別計算它左右子樹的高度 int leftDepth = TreeDepth(root->left); int rightDepth = TreeDepth(root->right); // 計算左右子樹的高度差 int ret = leftDepth > rightDepth ? leftDepth - rightDepth : rightDepth - leftDepth; // 高度差不超過1,才能繼續(xù)往下遞歸遍歷當(dāng)前樹的左右子樹 return ret <= 1 && isBalanced(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ù)。空間復(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)用一次。因為到達(dá)左子樹底部后,每次對應(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ù):int abs( int n ); ,頭文件 <stdlib.h> or <math.h>。
遞歸過程演示:自底向上遞歸類似于后序遍歷
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ // 計算當(dāng)前樹的高度,并判斷當(dāng)前樹是否是平衡二叉樹 int _isBalanced(struct TreeNode* root) { // 先分別判斷當(dāng)前樹的左/右子樹是否平衡 // 如果當(dāng)前樹的左/右子樹中只要有一個不平衡,則全樹就不平衡,返回-1(表示不平衡) // 如果當(dāng)前樹的左右子樹都平衡,則繼續(xù)判斷當(dāng)前樹是否平衡 // 1. 到葉子節(jié)點了,當(dāng)前樹根節(jié)點為空,說明是平衡的,則返回高度0 if(root == NULL) { return 0; } // 2. 當(dāng)前樹根節(jié)點不為空 // 計算左右子樹的高度 int leftTreeDepth = _isBalanced(root->left); int rightTreeDepth = _isBalanced(root->right); // 不平衡的3種情況:左子樹高度為-1,右子樹高度為-1,左右子樹高度差>1 if(leftTreeDepth == -1 || rightTreeDepth == -1 || abs(leftTreeDepth - rightTreeDepth) > 1) { return -1; } // 如果不滿足上面3種情況,說明當(dāng)前樹是平衡的,返回當(dāng)前樹的高度 return leftTreeDepth > rightTreeDepth ? leftTreeDepth + 1 : rightTreeDepth + 1; } bool isBalanced(struct TreeNode* root){ // 遞歸遍歷過程中: // 只要有一個子樹高度為-1,說明整個樹是不平衡的,返回false // 所有子樹高度都不等于-1,說明整個樹是平衡的,返回true return _isBalanced(root) != -1; }
復(fù)雜度分析:
1.時間復(fù)雜度:O(n),其中 n 是二叉樹中的節(jié)點個數(shù)。
最壞情況是二叉樹為滿二叉樹時,需要遍歷完滿二叉樹中的所有節(jié)點,自底向上方法,因此每個節(jié)點只會被遍歷一次,所以時間復(fù)雜度是 O(n)。
2.空間復(fù)雜度:O(n),其中 n 是二叉樹中的節(jié)點個數(shù)??臻g復(fù)雜度卻決于遞歸調(diào)用的層數(shù),有 n 個節(jié)點的二叉樹為單邊樹時深度最大,為 n。
到此這篇關(guān)于C語言平衡二叉樹真題練習(xí)的文章就介紹到這了,更多相關(guān)C語言平衡二叉樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
數(shù)據(jù)結(jié)構(gòu)與算法中二叉樹子結(jié)構(gòu)的詳解
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)與算法中二叉樹子結(jié)構(gòu)的詳解的相關(guān)資料,需要的朋友可以參考下2017-04-04

C語言二叉樹常見操作詳解【前序,中序,后序,層次遍歷及非遞歸查找,統(tǒng)計個數(shù),比較,求深度】

QT中QStringListModel類的應(yīng)用介紹