二叉樹問題（四）-LeetCode 502、543、637、606、114、979（最大堆，IPO）
- 2019 年 12 月 24 日
- 筆記
作者：TeddyZhang，公眾號：算法工程師之路
二叉樹問題（四）：
LeetCode # 502 543 637 606 114 979
1
編程題
【LeetCode #502】IPO
假設 力扣（LeetCode）即將開始其 IPO。為了以更高的價格將股票賣給風險投資公司，力扣 希望在 IPO 之前開展一些項目以增加其資本。由於資源有限，它只能在 IPO 之前完成最多 k 個不同的項目。幫助 力扣 設計完成最多 k 個不同項目後得到最大總資本的方式。 給定若干個項目。對於每個項目 i，它都有一個純利潤 Pi，並且需要最小的資本 Ci 來啟動相應的項目。最初，你有 W 資本。當你完成一個項目時，你將獲得純利潤，且利潤將被添加到你的總資本中。 總而言之，從給定項目中選擇最多 k 個不同項目的列表，以最大化最終資本，並輸出最終可獲得的最多資本。
示例 1:
輸入: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1]. 輸出: 4
解題思路：
其是一個貪心思路，當我們有W的資本，我們每次肯定會投利潤最大且資本足夠的那個項目，因此， 對資本費用建立一個最小堆，對獲得利潤建立最大堆，每次投資時，從最小堆中取出所有小於等於W的項目， 並壓入最大堆，然後取出一個 最大堆堆頂的項目，即為本次投資的項目，本題中需要投資k次，但注意有可能因為 資本不足，達不到k次，因此在最大堆為空時，返回結果！
class Solution { public: int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) { using Pair = pair<int, int>; // cost, profit auto cmp1 = [](const Pair& a, const Pair& b) { return a.first > b.first; // minheap of mincost }; auto cmp2 = [](const Pair& a, const Pair& b) { return a.second < b.second; // maxheap of maxprofit; }; priority_queue<Pair, vector<Pair>, decltype(cmp1)> mincost(cmp1); priority_queue<Pair, vector<Pair>, decltype(cmp2)> maxprofit(cmp2); for(int i = ; i < Profits.size(); i++) { mincost.push(make_pair(Capital[i], Profits[i])); } while(k--) { while (!mincost.empty() && mincost.top().first <= W) { maxprofit.push(mincost.top()); mincost.pop(); } if (maxprofit.empty()) return W; W += maxprofit.top().second; maxprofit.pop(); } return W; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/ipo
【LeetCode #543】二叉樹的直徑
給定一棵二叉樹，你需要計算它的直徑長度。一棵二叉樹的直徑長度是任意兩個結點路徑長度中的最大值。這條路徑可能穿過根結點。
解題思路：
二叉樹的直徑其實質為某棵二叉樹的左右子樹的最大深度之和！
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int diameterOfBinaryTree(TreeNode* root) { if (root == nullptr) return ; maxDepth(root); return maxLength; } private: int maxLength = ; int maxDepth(TreeNode* root) { if (root == nullptr) return ; int l = maxDepth(root->left); int r = maxDepth(root->right); maxLength = max(maxLength, l + r); return + max(l, r); } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/diameter-of-binary-tree/
【LeetCode #637】二叉樹的層平均值
給定一個非空二叉樹, 返回一個由每層節點平均值組成的數組.
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<double> averageOfLevels(TreeNode* root) { vector<double> res; if (root == nullptr) return res; queue<TreeNode*> que; que.push(root); while(!que.empty()) { int size = que.size(); int n = size; double tmp = ; while(size--) { TreeNode* node = que.front(); que.pop(); tmp += (node->val); if (size == ) res.push_back(tmp / n); if (node->left) que.push(node->left); if (node->right) que.push(node->right); } } return res; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/
【LeetCode #606】根據二叉樹創建字符串
你需要採用前序遍歷的方式，將一個二叉樹轉換成一個由括號和整數組成的字符串。 空節點則用一對空括號 "()" 表示。而且你需要省略所有不影響字符串與原始二叉樹之間的一對一映射關係的空括號對。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: string tree2str(TreeNode* t) { if (t == nullptr) return ""; if (t->right) return to_string(t->val) + "(" + tree2str(t->left) + ")(" + tree2str(t->right) + ")"; if (t->left) return to_string(t->val) + "(" + tree2str(t->left) + ")"; if (!t->left && !t->right) return to_string(t->val); return ""; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/construct-string-from-binary-tree
【LeetCode #114】二叉樹展開為鏈表
給定一個二叉樹，原地將它展開為鏈表。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* last = nullptr; void flatten(TreeNode* root) { if (root == nullptr) return; flatten(root->right); flatten(root->left); root->right = last; root->left = nullptr; last = root; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/
【LeetCode #979】在二叉樹中分配硬幣
給定一個有 N 個結點的二叉樹的根結點 root，樹中的每個結點上都對應有 node.val 枚硬幣，並且總共有 N 枚硬幣。 在一次移動中，我們可以選擇兩個相鄰的結點，然後將一枚硬幣從其中一個結點移動到另一個結點。(移動可以是從父結點到子結點，或者從子結點移動到父結點。)。 返回使每個結點上只有一枚硬幣所需的移動次數。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int res = ; int distributeCoins(TreeNode* root) { dfs(root); return res; } private: int dfs(TreeNode* root) { if (root == nullptr) return ; int l = dfs(root->left); // 負數表示左節點需要扣除的金幣數，需要從根節點搬下去 int r = dfs(root->right); // 正數表示左節點需要搬移的金幣數，需要將多餘的節點搬上去 res += abs(l) + abs(r); return l + r + root->val - ; } };
來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/distribute-coins-in-binary-tree
