C語(yǔ)言平衡二叉樹真題練習(xí)
題目難度:簡(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,不用往下遞歸了。
遞歸過程演示:自頂向下的遞歸類似于前序遍歷
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ // 計(jì)算當(dāng)前任意一個(gè)節(jié)點(diǎn)(樹)的高度(子函數(shù)) int TreeDepth(struct TreeNode* root) { // 當(dāng)前節(jié)點(diǎn)為空 if(root == NULL) { return 0; } // 當(dāng)前節(jié)點(diǎn)不為空,分別計(jì)算它的左右子樹的高度 int leftDepth = TreeDepth(root->left); int rightDepth = TreeDepth(root->right); // 當(dāng)前節(jié)點(diǎn)(樹)的高度 return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; } bool isBalanced(struct TreeNode* root){ // 依次遞歸遍歷完root的所有子樹,分別判斷當(dāng)前子樹是否為高度平衡二叉樹 // 當(dāng)前樹的根節(jié)點(diǎn)為空,說明其滿足高度平衡的二叉樹,返回true if(root == NULL) { return true; } // 當(dāng)前樹的根節(jié)點(diǎn)不為空,分別計(jì)算它左右子樹的高度 int leftDepth = TreeDepth(root->left); int rightDepth = TreeDepth(root->right); // 計(jì)算左右子樹的高度差 int ret = leftDepth > rightDepth ? leftDepth - rightDepth : rightDepth - leftDepth; // 高度差不超過1,才能繼續(xù)往下遞歸遍歷當(dāng)前樹的左右子樹 return ret <= 1 && isBalanced(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)度中的,每次只需要獲取新的右子樹長(zhǎng)度便可。
自底向上遞歸類似于 后序遍歷,對(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ù):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; * }; */ // 計(jì)算當(dāng)前樹的高度,并判斷當(dāng)前樹是否是平衡二叉樹 int _isBalanced(struct TreeNode* 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) { return 0; } // 2. 當(dāng)前樹根節(jié)點(diǎn)不為空 // 計(jì)算左右子樹的高度 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){ // 遞歸遍歷過程中: // 只要有一個(gè)子樹高度為-1,說明整個(gè)樹是不平衡的,返回false // 所有子樹高度都不等于-1,說明整個(gè)樹是平衡的,返回true return _isBalanced(root) != -1; }
復(fù)雜度分析:
1.時(shí)間復(fù)雜度:O(n),其中 n 是二叉樹中的節(jié)點(diǎn)個(gè)數(shù)。
最壞情況是二叉樹為滿二叉樹時(shí),需要遍歷完滿二叉樹中的所有節(jié)點(diǎn),自底向上方法,因此每個(gè)節(jié)點(diǎn)只會(huì)被遍歷一次,所以時(shí)間復(fù)雜度是 O(n)。
2.空間復(fù)雜度:O(n),其中 n 是二叉樹中的節(jié)點(diǎn)個(gè)數(shù)。空間復(fù)雜度卻決于遞歸調(diào)用的層數(shù),有 n 個(gè)節(jié)點(diǎn)的二叉樹為單邊樹時(shí)深度最大,為 n。
到此這篇關(guān)于C語(yǔ)言平衡二叉樹真題練習(xí)的文章就介紹到這了,更多相關(guān)C語(yǔ)言平衡二叉樹內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(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語(yǔ)言二叉樹常見操作詳解【前序,中序,后序,層次遍歷及非遞歸查找,統(tǒng)計(jì)個(gè)數(shù),比較,求深度】

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