第32题:
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。(来自LeetCode)
说明: 叶子节点是指没有子节点的节点。
1、第一种法子就是递归求出最小深度。
2、还有一种就是利用层次遍历来遍历所有树节点;
当遍历到第一个左右节点都为空时就返回这个节点的层数,就是这棵树的最小深度。
第50题:
实现 pow(x, n) ,即计算 x 的 n 次幂函数。(来自LeetCode)
1、x的n次幂,就是n个x相乘;
其实按思路就可以直接递归返回pow(x,n-1)*x,行不通;
也可以直接for循环得出n个x的乘积;
也超出时间限制了;
还有一种递归优化,
就是如果 n 是偶数,我们将 n 折半,底数变为 x^2;
如果 n 是奇数, 我们将 n 减去 1 ,底数不变,得到的结果再乘上底数 x;
这样递归得出结果。
也可以迭代求出结果。