二叉树问题（四）-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
