二叉樹（七）：二叉樹的高度與平衡二叉樹

一、二叉樹的深度與高度

1、二叉樹的深度

對于二叉樹中的某個節點，其深度是從根節點到該節點的最長簡單路徑所包含的節點個數，是從上面向下面數的。是以通路某個節點的深度要使用先序周遊

2、二叉樹的高度

對于二叉樹中的某個節點其高度是從葉子節點到該節點的最長簡單路徑包含的節點個數，是從下面向上面數的。是以通路某個節點的高度需要使用後續周遊

3、二叉樹的深度與高度辨析

每層節點的深度和高度如圖所示：

4、二叉樹的深度與高度的聯系

一個二叉樹根節點的高度就是這個二叉樹的最大深度

二、二叉樹的高度

1、遞歸法

遞歸三要素：

1. 遞歸傳回值和參數：傳回值為目前節點的高度，參數為目前節點
2. 遞歸單層邏輯：目前節點高度 = 1 + max（左子樹高度，右子樹高度）
3. 遞歸終止條件：目前節點為空，傳回高度為0，結束遞歸

2、遞歸法代碼

class Solution {
public:
	//遞歸參數及傳回值
    int height(TreeNode* root) {
    
    	//遞歸終止條件
        if(root == nullptr) return 0;
        
        //單層遞歸邏輯
        int leftheight = height(root->left);
        int rightheight = height(root->right);
        return 1 + max(leftheight , rightheight );
    }
};
           

三、平衡二叉樹

110.平衡二叉樹

平衡二叉樹定義：一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1。

1、遞歸法解題思路

給定一個節點，分别求取其左右孩子為根節點的子樹的高度，相比較是否相差1。而一旦有子樹不為平衡二叉樹的時候，該結果需要遞歸傳遞，最後輸出整棵樹不是平衡二叉樹

1. 遞歸傳回值和參數：遞歸傳回值為目前節點為根節點的二叉樹高度，目前二叉樹是否為平衡二叉樹，參數為目前節點
2. 單層遞歸邏輯：目前節點二叉樹高度 = 1 + max(左子樹高度，右子樹高度)；目前節點是否為平衡二叉樹 = 左子樹高度與右子樹高度內插補點是否大于1
3. 遞歸結束條件：目前節點為空，二叉樹高度為0，目前節點時平衡二叉樹

優化：我們可以利用樹木的高度為-1來表示子樹不是平衡二叉樹，進而減少傳回參數

2、遞歸法解題代碼

class Solution {
public:
	//遞歸傳回值和參數
    int treeheight(TreeNode* root){
    
    	//遞歸終止條件
        if(root == nullptr) return 0;
        
		//單層遞歸邏輯
		//擷取左右樹高度，如果左右樹已經存在不平衡，遞歸終止，直接傳回-1
        int leftheight = treeheight(root->left);
        if(leftheight == -1) return -1;
        int rightheight = treeheight(root->right);
        if(rightheight == -1) return -1;
		//如果左右樹不存在不平衡，根據左右樹高度計算目前節點是否平衡，以傳回目前高度或-1
        if(abs(leftheight - rightheight) > 1) return -1;
        return 1 + max(leftheight, rightheight);
    }
    bool isBalanced(TreeNode* root) {
    	//調用遞歸判定是否為平衡二叉樹
        if(treeheight(root) != -1) return true;
        return false;
    }
};