C++ 编程练习题: 左子树叶节点之和 (深度优先搜索+广度优先搜索+递归算法)
题意: 找出所有左子树上的叶节点的值之和. 3 / \ 9 20 / \ 15 7 比如上面 9 和15是左子树上的子节点, 那么求和得 24. 一般来说, 遍历树有两种方式: 深度优先DFS和广度优先BFS. 解这题的关键就在需要知道叶子节点是从左边来的还是从右边来的. C++ 定义二叉树 struct TreeNode { int val; TreeNode *left; …
Tag: 练习题
C++ 编程练习题 – 最多水容器 (递归)
题意: 给定一个数组, 每个数值代表柱子的高度, 那么求出这些柱子最多可以装多少水. 水的体积由较短的长度乘以两个柱子的距离. 上面的图的输入为 . 蓝色区域最可以装水为49. 最简单的方法就是暴力穷举, 那么复杂度为 O(n^2) , 需要穷举n*(n-1)/2对高度. 可以用递归来实现, 但是递归需要额外O(n) 的空间 – 调用堆栈: class Solution { public: int f(vector<int>& height, int j) { if …