C語(yǔ)言平衡二叉樹(shù)問(wèn)題怎么解決

這篇文章主要介紹“C語(yǔ)言平衡二叉樹(shù)問(wèn)題怎么解決”的相關(guān)知識(shí)，小編通過(guò)實(shí)際案例向大家展示操作過(guò)程，操作方法簡(jiǎn)單快捷，實(shí)用性強(qiáng)，希望這篇“C語(yǔ)言平衡二叉樹(shù)問(wèn)題怎么解決”文章能幫助大家解決問(wèn)題。

一、題目描述

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

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

二、解題思路

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

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

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

核心思路

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

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

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

• 如果不超過(guò)，才能繼續(xù)往下遞歸遍歷「當(dāng)前樹(shù)的左右子樹(shù)」，判斷其是否平衡；

• 如果超過(guò)1，說(shuō)明不滿足平衡條件，則直接返回 false，不用往下遞歸了。

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// 計(jì)算當(dāng)前任意一個(gè)節(jié)點(diǎn)(樹(shù))的高度（子函數(shù)）
int TreeDepth(struct TreeNode* root)
{
    // 當(dāng)前節(jié)點(diǎn)為空
    if(root == NULL)
    {
        return 0;
    }
    // 當(dāng)前節(jié)點(diǎn)不為空，分別計(jì)算它的左右子樹(shù)的高度
    int leftDepth = TreeDepth(root->left);
    int rightDepth = TreeDepth(root->right);
    // 當(dāng)前節(jié)點(diǎn)(樹(shù))的高度
    return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
bool isBalanced(struct TreeNode* root){
    // 依次遞歸遍歷完root的所有子樹(shù)，分別判斷當(dāng)前子樹(shù)是否為高度平衡二叉樹(shù)
    // 當(dāng)前樹(shù)的根節(jié)點(diǎn)為空，說(shuō)明其滿足高度平衡的二叉樹(shù)，返回true
    if(root == NULL)
    {
        return true;
    }
    // 當(dāng)前樹(shù)的根節(jié)點(diǎn)不為空，分別計(jì)算它左右子樹(shù)的高度
    int leftDepth = TreeDepth(root->left);
    int rightDepth = TreeDepth(root->right);
    // 計(jì)算左右子樹(shù)的高度差
    int ret = leftDepth > rightDepth ? leftDepth - rightDepth : rightDepth - leftDepth;
    // 高度差不超過(guò)1，才能繼續(xù)往下遞歸遍歷當(dāng)前樹(shù)的左右子樹(shù)
    return ret <= 1 && isBalanced(root->left) && isBalanced(root->right);
}

復(fù)雜度分析：

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

最壞情況下，二叉樹(shù)是滿二叉樹(shù)，主函數(shù) isBalanced(root) 需要遍歷二叉樹(shù)中的所有節(jié)點(diǎn)，時(shí)間復(fù)雜度是 O(n)。計(jì)算每個(gè)子樹(shù)的最大高度函數(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 是二叉樹(shù)中的節(jié)點(diǎn)個(gè)數(shù)。空間復(fù)雜度主要取決于遞歸調(diào)用的層數(shù)，遞歸調(diào)用的層數(shù)不會(huì)超過(guò) n。

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

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

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

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

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

• 如果當(dāng)前樹(shù)是平衡的，則返回其高度，否則返回 -1（表示不平衡）。

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

• 整個(gè)遞歸的終止條件：遞歸應(yīng)該在什么時(shí)候結(jié)束？— 子樹(shù)根節(jié)點(diǎn)為空的時(shí)候，空樹(shù)也是平衡二叉樹(shù)。

• 本級(jí)遞歸應(yīng)該做什么？ — 判斷當(dāng)前樹(shù)的左子樹(shù)、右子樹(shù)、以及當(dāng)前樹(shù)是否是平衡的。

• 返回值：應(yīng)該返回給上一級(jí)的返回值是什么？— 當(dāng)前樹(shù)是平衡的，則返回其高度，不平衡則返回 -1。

遞歸算法流程：

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

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

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

• 如果「左子樹(shù) left 高度為 -1」、或「右子樹(shù) right 高度為 -1」、或「左右子樹(shù)高度差 > 1」，說(shuō)明整個(gè)樹(shù) 不平衡 ，直接返回 -1（表示不平衡）。

• 如果不滿足上面 3 種情況，說(shuō)明當(dāng)前樹(shù)是 平衡 的，返回當(dāng)前樹(shù)的高度，即 max ( left, right ) + 1 。

補(bǔ)充：計(jì)算絕對(duì)值的函數(shù)：int abs( int n ); ，頭文件 <stdlib.h> or <math.h>。

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// 計(jì)算當(dāng)前樹(shù)的高度，并判斷當(dāng)前樹(shù)是否是平衡二叉樹(shù)
int _isBalanced(struct TreeNode* root)
{
    // 先分別判斷當(dāng)前樹(shù)的左/右子樹(shù)是否平衡
    // 如果當(dāng)前樹(shù)的左/右子樹(shù)中只要有一個(gè)不平衡，則全樹(shù)就不平衡，返回-1（表示不平衡）
    // 如果當(dāng)前樹(shù)的左右子樹(shù)都平衡，則繼續(xù)判斷當(dāng)前樹(shù)是否平衡
    // 1. 到葉子節(jié)點(diǎn)了，當(dāng)前樹(shù)根節(jié)點(diǎn)為空，說(shuō)明是平衡的，則返回高度0
    if(root == NULL)
    {
        return 0;
    }
    // 2. 當(dāng)前樹(shù)根節(jié)點(diǎn)不為空
    // 計(jì)算左右子樹(shù)的高度
    int leftTreeDepth = _isBalanced(root->left);
    int rightTreeDepth = _isBalanced(root->right);
    // 不平衡的3種情況：左子樹(shù)高度為-1，右子樹(shù)高度為-1，左右子樹(shù)高度差>1
    if(leftTreeDepth == -1 || rightTreeDepth == -1 || abs(leftTreeDepth - rightTreeDepth) > 1)
    {
        return -1;
    }
    // 如果不滿足上面3種情況，說(shuō)明當(dāng)前樹(shù)是平衡的，返回當(dāng)前樹(shù)的高度
    return leftTreeDepth > rightTreeDepth ? leftTreeDepth + 1 : rightTreeDepth + 1;
}
bool isBalanced(struct TreeNode* root){
    // 遞歸遍歷過(guò)程中：
    // 只要有一個(gè)子樹(shù)高度為-1，說(shuō)明整個(gè)樹(shù)是不平衡的，返回false
    // 所有子樹(shù)高度都不等于-1，說(shuō)明整個(gè)樹(shù)是平衡的，返回true
    return _isBalanced(root) != -1;
}

復(fù)雜度分析：

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

最壞情況是二叉樹(shù)為滿二叉樹(shù)時(shí)，需要遍歷完滿二叉樹(shù)中的所有節(jié)點(diǎn)，自底向上方法，因此每個(gè)節(jié)點(diǎn)只會(huì)被遍歷一次，所以時(shí)間復(fù)雜度是 O(n)。

2.空間復(fù)雜度：O(n)，其中 n 是二叉樹(shù)中的節(jié)點(diǎn)個(gè)數(shù)?？臻g復(fù)雜度卻決于遞歸調(diào)用的層數(shù)，有 n 個(gè)節(jié)點(diǎn)的二叉樹(shù)為單邊樹(shù)時(shí)深度最大，為 n。

關(guān)于“C語(yǔ)言平衡二叉樹(shù)問(wèn)題怎么解決”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。