[leetcode]3319. K-th Largest Perfect Subtree Size in Binary Tree

Benjamin

2024 年 12 月 29 日

IPFS

請取得一個二元樹上，第K大的完全二元樹的節點數量。

※：這題是leetcode週賽419th的題目

二元樹是一種資料結構，每個節點(Node)最多有兩個子節點(left, right)，而子節點又可以有自己的子節點……，這樣的節點組成就是二元樹，其中第一個節點稱為根(root node)，沒有子節點的節點就叫做葉(leaf node)。

完全二元樹(Perfect binary tree)的定義是「每個leaf的層樹(到root的距離)相同，而且leaf以外的所有節點都有left, right兩個子節點」。

題目：3319. K-th Largest Perfect Subtree Size in Binary Tree
關鍵字：演算法、二元樹、遞迴

第一版

首先是準備測試資料，先照著題目的註解寫出TreeNode的結構方便測試，如下圖。

原本的題目範例(右上)，建立樹結構的程式(左上)、嘗試執行後印出的各節點路徑和樹值(下)

接著就是開始解題了。首先是關於完全二元樹的特性，「完全二元樹底下的每個子樹都是完全二元樹，所以一節點的左右子樹只要有一個不符合它就不是完全二元樹」、「每個leaf節點都是大小為1的完全二元樹」，因此從leaf節點往上判斷它的父節點還是不是完全二元樹，直到根節點為止每個點都檢查一遍，就可以得到總共有多少完全二元樹，以及個別的大小。

以下開始解題，照著題目的規則寫出檢查邏輯

// 完全二元樹的大小為1, 3, 7...，規則為「2的n次方-1」，所以只要計算深度就行。
// 同樣大小的二元樹沒有區別，記錄每深度的完全二元樹出現次數。
private SortedMap<Integer, Integer> result;

// 記錄總共的完全二元樹數量
private int perfectTreeCount;

private int countTreeNodesDepth(TreeNode root) {
    // 子節點不存在不會列入計算，例如左子節點不存在表示左子樹的大小為0。
    if (root == null)
        return 0;

    // 每個節點要判斷是否為完全二元樹需要等左右仔節點的判斷都完成才能進行。
    int leftDepth = countTreeNodesDepth(root.left);
    int rightDepth = countTreeNodesDepth(root.right);

    // 如果任一個子節點的子樹不是完全二元樹，或者兩個子樹的大小不同，都代表這個節點範圍內的子樹並不是完全二元樹(回傳-1)。
    if (leftDepth == -1 || leftDepth != rightDepth)
        return -1;

    // 符合的二元樹深度就是子樹深度再加1。
    int nowDepth = leftDepth + 1;

    // 記錄完全二元樹總數和該大小多一個，
    result.merge(nowDepth, 1, Integer::sum);
    perfectTreeCount++;

    return nowDepth;
}