算法通关 - 二叉树遍历 递归&分治
二叉树遍历的三种方式
-
前序遍历（根左右）
前序遍历.png
public static class TreeNode{
int data;
TreeNode leftChild;
TreeNode rightChild;
TreeNode(int data){
this.data = data;
}
}
public static void preOrder(TreeNode root){
if(root == null) return;
System.out.println(root.data);
preOrder(root.leftChild);
preOrder(root.rightChild);
}
-
中序遍历（左根右）
中序遍历.png
public static void inOrder(TreeNode root){
if(root == null) return;
inOrder(root.leftChild);
System.out.println(root.data);
inOrder(root.rightChild);
}
-
后序遍历（左右根）
后序遍历.png
public static void postOrder(TreeNode root){
if(root == null) return;
postOrder(root.leftChild);
postOrder(root.rightChild);
System.out.println(root.data);
}
前序遍历就是根在最前面，中序遍历是根在中间，后序遍历则是根在最后。这样就很容易记住了
递归（Recursion）
递归也是一种循环，但它不是通过定义一个for循环，而是通过函数体自己调用自己来实现一种循环的状态。比如计算n的阶乘n! = 1 * 2 * 3....*n 就可以通过递归来做，代码如下：
public int factorial(int n){
if(n <= 1) return 1;
return n * factorial(n - 1);
}
递归的模板代码:
def recursion(level,param1,param2,....):
//递归终止条件，必须要有，否则就是死循环
if level > MAX_LEVEL:
print_result
return
//在当前的level处理代码逻辑
procress_data(level,data...)
//递归调用
self.recursion(level + 1,p1,....)
//按照实际情况，如果需要就进行reverse_state的收尾工作
reverse_state(level)
斐波那契数列：1，1，2，3，5，8，13，21... f (n) = f (n - 1) + f (n - 2)
递归过程如下：
斐波那契数列.png
我们会发现在递归的过程中很多计算是重复的，比如在计算f (5) 和 f (6)的时候都会计算f (4)，这样f (4)就计算了两次，所以有时候递归解决问题并不是高效的。因此就出现了很多基于递归的高级算法，比如下面要说的分治。
分治（Divide&Conquer）
分治的思想就是先把一个大的问题分解成一个个的子问题，然后再对子问题进行一一解决，最后将每个子结果合并得到最终的结果。
分治逻辑图.png
例如，给一个全是小写的从a - j 的字符串，把其中的每个字符变成大写。可以通过for循环对每个字符进行大写操作。也可以通过递归，每次把当前的字符变成大写，把剩下的字符放到递归中去。使用分治的话，就是把字符串分成多个子问题，每个子问题是一个字母，我们要做的就是把每个子问题中的单个字母变成大写，最后把结果合并起来。这样的好处就是可以进行并行计算，提高效率，因为每个子问题是互不相关的。
小写字符串转换为大写字符串.png
递归适用于解决的问题是没有所谓的中间结果，也就是没有重复计算。如果有大量重复计算的话，分治的效率可能并不高，这时候就需要考虑更适合的算法，比如动态规划。
分治代码模板：
def divide_conquer(problem,param1,param2,....):
//递归终止条件，必须要有，否则就是死循环
if problem is None:
print_result
return
//准备数据，把当前的大问题拆分成子问题
data = prepare_data(problem)
subproblems = split_problem(problem,data)
//对子问题进行处理，得到每一个子问题的子结果
subresult1 = self.divide_conquer(subproblems[0],p1,....)
subresult2 = self.divide_conquer(subproblems[1],p1,....)
subresult3 = self.divide_conquer(subproblems[2],p1,....)
...
//对子结果进行合并
result = process_result(subresult1,subresult2,subresult3...)
1.实现 pow(x, n) ，即计算 x 的 n 次幂函数（LeetCode - 50）
示例如下：
- -100.0 < x < 100.0
- n 是 32 位有符号整数
输入: 2.00000, 10
输出: 1024.00000
输入: 2.10000, 3
输出: 9.26100
输入: 2.00000, -2
输出: 0.25000
方法一：暴力法，直接将 x 连乘 n 次，需要考虑 n > 0 和 n < 0的情况
class Solution {
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double ans = 1;
for (long i = 0; i < N; i++)
ans = ans * x;
return ans;
}
}
- 时间复杂度：O(n). 我们需要将
x连乘n次。 - 空间复杂度：O(1). 我们只需要一个变量来保存最终
x的连乘结果。
方法二：快速幂算法（递归）
假定我们已经得到了 x ^ (n / 2) 的结果，并且我们现在想得到 x ^ n的结果。我们令 A 是 x ^ (n / 2)的结果，我们可以根据 n 的奇偶性来分别讨论 x ^ n的值。如果 n 为偶数，我们可以用公式 (x ^ n) ^ 2 = x ^ (2 * n)来得到 x ^ n = A * A。如果 n 为奇数，那么 A * A = x ^ (n - 1)。直观上看，我们需要再乘一次 x ，即 x ^ n = A * A * x 。该方法可以很方便的使用递归实现。我们称这种方法为 "快速幂"，因为我们只需最多 O(logn) 次运算来得到 x ^ n
class Solution {
private double fastPow(double x, long n) {
if (n == 0) {
return 1.0;
}
double half = fastPow(x, n / 2);
if (n % 2 == 0) {
return half * half;
} else {
return half * half * x;
}
}
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
return fastPow(x, N);
}
}
- 时间复杂度：O(logn). 每一次我们使用公式 (x ^ n) ^ 2 = x ^ (2 * n), n 都变为原来的一半。因此我们需要至多 O(logn) 次操作来得到结果。
- 空间复杂度：O(logn). 每一次计算，我们需要存储 x ^ (n / 2) 的结果。 我们需要计算O(logn) 次，所以空间复杂度为O(logn) 。
方法三：快速幂算法（循环）
思路： x^n 等价于 (x * x) ^ (n/2) 【如果n除以2余1就得在后面乘以一个x补上】, 继续等价于 (x^2 * x^2) ^ (n/4) 【如果n除4余1再乘以一个x^2补上】，用纯文字描述就是随着n不断地除以2减小，x不断地平方来扩大，直到n为1结束，这个时候的x就是最后的结果了，但是每次循环都要对n为奇数的情况做一个填补。因为x是以不断平方自己的方式来到达最后的终点，所以复杂度是logN
class Solution {
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double ans = 1;
double current_product = x;
for (long i = N; i > 0; i /= 2) {
if ((i % 2) == 1) {
ans = ans * current_product;
}
current_product = current_product * current_product;
}
return ans;
}
}
class Solution {
public double myPow(double x, int n) {
long N = n;
if (N < 0) {
x = 1 / x;
N = -N;
}
double result = 1.0;
double base = x;
while (N != 0) {
//用(N & 1) != 0 来判断二进制位最后位0或1，也就是判断它的奇偶性
if ((N & 1) != 0){
result *= base;
}
base *= base;
N >>= 1;
}
return result;
}
}
- 时间复杂度：O(logn). 对每一个 n 的二进制位表示，我们都至多需要累乘 1 次，所以总的时间复杂度为 O(logn) 。
- 空间复杂的：O(1). 我们只需要用到 2 个变量来保存当前的乘积和最终的结果 x 。
2.求众数（LeetCode - 169）
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
方法一：暴力法
遍历整个数组，然后用另一重循环统计每个数字出现的次数。将出现次数超过n/2的元素返回。
class Solution {
public int majorityElement(int[] nums) {
int majorityCount = nums.length/2;
for (int num : nums) {
int count = 0;
for (int elem : nums) {
if (elem == num) {
count += 1;
}
}
if (count > majorityCount) {
return num;
}
}
return -1;
}
}
- 时间复杂度：O(n^2) 包含两重嵌套的 for 循环，每一层 n 次迭代，所以总的是平方级的时间复杂度。
- 空间复杂度：O(1) 没有分配任何与输入规模成比例的额外的空间
方法二：哈希表
使用哈希表来存储每个元素，然后用一个循环在线性时间内遍历 nums ，我们只需要返回有最大值的键。
class Solution {
public int majorityElement(int[] nums) {
int majority = nums.length / 2;
Map<Integer, Integer> numCount = new HashMap<>();
for (int num : nums) {
int count = numCount.getOrDefault(num, 0) + 1;
if (count > majority) return num;
numCount.put(num, count);
}
return -1;
}
}
- 时间复杂度：O(n) nums 迭代一次，哈希表的插入是常数时间的。所以总时间复杂度为 O(n)
- 空间复杂度：O(n)
方法三：排序
如果所有数字被单调递增或者单调递减的顺序排了序，那么众数的下标为 (n/2) 当 n 是偶数时，下标为 (n/2) + 1
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
- 时间复杂度：O(N*logN)
- 空间复杂度：O(1)或者 O(n)
我们将 nums 就地排序，如果不能就低排序，我们必须使用线性空间将 nums 数组拷贝，然后再排序。
方法四：分治
如果我们分别知道数组左边一半和右边一半的众数，左右两边众数相等那么就直接找到了，如果不相等就查找两边众数出现次数更多的那一个。
我们使用经典的分治算法递归求解，直到所有的子问题都是长度为 1 的数组。由于传输子数组需要额外的时间和空间，所以我们实际上只传输子区间的左右指针 lo 和 hi 表示相应区间的左右下标。长度为 1 的子数组中唯一的数显然是众数，直接返回即可。如果回溯后某区间的长度大于 1 ，我们必须将左右子区间的值合并。如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。否则，我们需要比较两个众数在整个区间内出现的次数来决定该区间的众数。原问题的答案就是下标为 00 和 nn 之间的众数这一子问题。
class Solution {
private int countInRange(int[] nums, int num, int lo, int hi) {
int count = 0;
for (int i = lo; i <= hi; i++) {
if (nums[i] == num) {
count++;
}
}
return count;
}
private int majorityEleme***ec(int[] nums, int lo, int hi) {
// base case; the only element in an array of size 1 is the majority
// element.
if (lo == hi) {
return nums[lo];
}
// recurse on left and right halves of this slice.
int mid = (hi-lo)/2 + lo;
int left = majorityEleme***ec(nums, lo, mid);
int right = majorityEleme***ec(nums, mid+1, hi);
// if the two halves agree on the majority element, return it.
if (left == right) {
return left;
}
// otherwise, count each element and return the "winner".
int leftCount = countInRange(nums, left, lo, hi);
int rightCount = countInRange(nums, right, lo, hi);
return leftCount > rightCount ? left : right;
}
public int majorityElement(int[] nums) {
return majorityEleme***ec(nums, 0, nums.length-1);
}
}
-
时间复杂度：O(N*logN)
-
空间复杂度：O(logN)
