題目難度：簡單

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ù)?？臻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ù)：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)文章希望大家以后多多支持腳本之家！

最新評論