欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言平衡二叉樹真題練習(xí)

 更新時間:2022年04月24日 08:39:59   作者:CodeWinter  
平衡二叉樹又被稱為AVL樹(有別于AVL算法),且具有以下性質(zhì):它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1,并且左右兩個子樹都是一棵平衡二叉樹。本文將詳解介紹一下平衡二叉樹的原理與實現(xiàn),需要的可以參考一下

題目難度:簡單

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 不為空,計算左右子樹 leftright 的高度,并判斷:

  • 如果「左子樹 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)文章希望大家以后多多支持腳本之家!

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

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

    這篇文章主要介紹了C語言二叉樹常見操作,結(jié)合實例形式詳細(xì)分析了基于C語言的二叉樹前序,中序,后序,層次遍歷及非遞歸查找,統(tǒng)計個數(shù),比較,求深度等相關(guān)操作技巧與注意事項,需要的朋友可以參考下
    2018-04-04
  • C語言中時間的基本用法小結(jié)

    C語言中時間的基本用法小結(jié)

    處理時間是編程中經(jīng)常遇到的問題,C語言中提供了一些時間處理函數(shù),在此記錄下一些基本的用法。下面這篇文章主要給大家介紹了C語言中關(guān)于時間的基本用法的相關(guān)資料,需要的朋友可以參考借鑒,感興趣的朋友們來一起看看吧。
    2017-01-01
  • QT中QStringListModel類的應(yīng)用介紹

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

    QStringListModel是最簡單的模型類,具備向視圖提供字符串?dāng)?shù)據(jù)的能力,本文主要介紹了QT中QStringListModel類的應(yīng)用介紹,具有一定的參考價值,感興趣的可以了解一下
    2024-01-01
  • C語言統(tǒng)計一串字符中空格鍵、Tab鍵、回車鍵、字母、數(shù)字及其他字符的個數(shù)(Ctrl+Z終止輸入)

    C語言統(tǒng)計一串字符中空格鍵、Tab鍵、回車鍵、字母、數(shù)字及其他字符的個數(shù)(Ctrl+Z終止輸入)

    這篇文章主要介紹了C語言統(tǒng)計一串字符中空格鍵、Tab鍵、回車鍵、字母、數(shù)字及其他字符的個數(shù)(Ctrl+Z終止輸入) ,需要的朋友可以參考下
    2018-03-03
  • C++中的友元函數(shù)與友元類詳情

    C++中的友元函數(shù)與友元類詳情

    這篇文章主要介紹了C++中的友元函數(shù)與友元類詳情,對類的封裝是C++三大特性中的一個重要特性,封裝好的數(shù)據(jù)在類的外部是訪問不到的但是一旦出了問題,想要操作被封裝的數(shù)據(jù)怎么辦呢?由此友元函數(shù)友元類誕生了,下文我們來詳細(xì)來接一下具體的有緣類吧
    2022-02-02
  • VS Code遠(yuǎn)程連接Linux服務(wù)器調(diào)試C程序的操作方法

    VS Code遠(yuǎn)程連接Linux服務(wù)器調(diào)試C程序的操作方法

    這篇文章主要介紹了VS Code遠(yuǎn)程連接Linux服務(wù)器調(diào)試C程序的操作方法,打開遠(yuǎn)程 Linux 服務(wù)器上的文件夾本文以 /root/ 為例,給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友參考下吧
    2023-12-12
  • Qt5 串口類QSerialPort的實現(xiàn)

    Qt5 串口類QSerialPort的實現(xiàn)

    在Qt5以上提供了QtSerialPort模塊,方便編程人員快速的開發(fā)應(yīng)用串口的應(yīng)用程序。本文主要介紹了Qt5 串口類QSerialPort的實現(xiàn),,感興趣的可以了解一下
    2022-05-05
  • 最新評論