莫里斯遍历二叉树

问题

1. 遍历二叉树
2. O(1)的时间复杂度
3. 二叉树的形状不能破坏

常规遍历

常规遍历使用递归，一般需要O(n)的空间复杂度和O(n)的时间复杂度。

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

解题报告

理解题意

• 两个数组：m & n （已排好序）
• 找到两个数组的中间节点
• 时间复杂度要求：\(\mathcal{O(log(m+n))}\)

理解例子

例子 1

• nums1：[1, 3]
• nums2：[2]
• 中间的元素为 2， 因为总共3个元素：1，2，3；

例子 2

• nums1：[1, 2]
• nums2：[3，4]
• 中间的元素为 2.5， 因为总共4个元素：[1，2，3，4]；（2+3）/2 = 2.5

思路

• 从例子来看，把两个数组的元素分别插入到一个新的数组，然后再遍历找到居中的元素，时间复杂度为\(\mathcal{O(m+n)}\)。
• 要求时间复杂度为 \(\mathcal{O(log(m+n))}\)，这个算是比较强烈的提示（对n个元素折半查找-BinarySearch就是 \(\mathcal{O(log(n))}\)）
• 顺着思路想：折半查找的问题就是如何使用折半查找找到需要的数，

// 非递归版本
int binarySearch(vector<int> &vec, int result){
  int l = 0, r = vec.size();
  while (l < r) {
     int mid = (r + l)/2;
     if (vec[mid] == result) return mid; // found the result
     if (vec[mid] > result) { // the index is on the left side of mid
         r = mid;
     } else {
         l = mid+1;
     }
  }
  return l;
}

// 递归版本
int binarySearch(vector<int> &vec, int l, int r, int result){
     int mid = (l + r) / 2;
     if (vec[mid] == result) return mid;
     if (vec[mid] > result) {
         return binarySearch(vec, l, mid, result);
     } else {
         return binarySearch(vec, mid+1, r, result);
     }
}

• 假定合并后的数组为C
• 从第一个数组取m1个元素，第二个元素取m2个元素，来构成前k个元素，来满足第k/k+1个元素就是中位数的候选数。其中k = m1 + m2 = (m + n + 1)/2。
• 找到的元素为 \(\mathcal{Avg(max(A[m-1], B[n-1]), min(A[m],B[n]))}\),根据总数奇数和偶数。
• 对左边的数组，在左边数组的区间内进行二分搜索， ，

流程

• 如果某一个为空，则返回另一个数组的中间元素即可
• 遍历完成后返回最大的长度
• 时间复杂度：线性时间 \(\mathcal{O(n)}\)

代码

class Solution {
public:
    int findMediaSortedArrays(vector<int> &nums1, vector<int> &nums2) {
        const int m = nums1.size();
        const int n = nums2.size();
        if (m > n) return findMediaSortedArrays(nums2, nums1);

    }
};

时间复杂度

如一开始分析：时间复杂度：线性时间 \(\mathcal{O(n)}\)

空间复杂度

额外申请了和一个链表，因此空间复杂度也为 \(\mathcal{O(max(len(l1), len(l2)))}\)