題目鏈接

題目描述 平衡二叉樹，顧名思義就是一棵“平衡”的二叉樹。在這道題中，“平衡”的定義為，對于樹中任意一個節點，都滿足左右子樹的高度差不超過 d. 空樹的高度定義為0，單個節點的高度為1，其他情況下樹的高度定義為根節點左右子樹高度最大值 + 1. 一棵在高度上平衡的樹，節點數可能不平衡，因此再定義一棵樹的不平衡度為這棵樹中所有節點的左右子樹的節點數之差的最大值。
給定平衡的定義參數d, 你需要求出所有高度為 n 的平衡樹中不平衡度的最大值。 輸入描述: 兩個整數，n, d.0 ≤ n, d ≤ 60 輸出描述: 一個整數：所有高度為 n 的平衡樹中不平衡度的最大值。 輸入 4 1 輸出 5 說明 下面這棵樹在 d=1 的定義下高度是平衡的，其不平衡度為 5。
題意 在保證二叉樹平衡的情況下，構造最大的不平衡度。 分析 首先貪心，最大的不平衡度應該在根節點，應該讓它的一棵子樹最大，另一棵最小。最大的子樹顯然是$$$2^{n-1}-1$$$；而最小的子樹，首先想到的是用一條$$$n-d-1$$$的鏈代替，但是對于這條鏈而言，還應該為每一個節點添加一個小分支，才能使的它是平衡的。
具體的來說，如果用$$$f(n)$$$表示構造一棵高度為$$$n$$$且幾乎是由鏈組成的平衡二叉樹的節點數，那么可以讓它的左子樹和右子樹一長一短，再加上它的根節點，就有$$$f(n)=1+f(n-1)+f(n-d-1)$$$，并且顯然當$$$n\le 0$$$時$$$f(n)=0$$$，即$$$ f(n)= \begin{cases} 0,& n<=0\\ 1+f(n-1)+f(n-d-1),&n>0\\ \end{cases} $$$
因為f(n)是一個常數，可以開一個dp數組來對f(n)記錄從而避免重復計算。 總結 似乎倒著推也行，似乎是有公式的，復雜度咋算啊。 代碼 #include<stdio.h> typedef long long LL; LL dp[65] = { 0,1 }; int n, d; LL build(int x) {if (x <= 0)return 0;if (dp[x]>0)return dp[x];dp[x] = 1+build(x - 1) + build(x - 1 - d);return dp[x]; }int main() {while (~scanf("%d %d", &n, &d)) {LL left = (1LL << (n - 1)) - 1;LL right = build(n - 1 - d);printf("%lld\n", left - right);} }

?

轉載于:https://www.cnblogs.com/tobyw/p/9737575.html

總結

以上是生活随笔為你收集整理的nowcoder 202F-平衡二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。