leedcode4

# 114. Flatten Binary Tree to Linked List

## Description

Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
1
/
2 5
/ \
3 4 6
The flattened tree should look like:

1

2

3

4

5

6

## Hints

If you notice carefully in the flattened tree, each node’s right child points to the next node of a pre-order traversal.

# 4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be$O(log (m+n))$.

You may assume nums1 and nums2 cannot be both empty.

## Method

cut A and B into two parts:

left_part right_part
A[0], A[1], …, A[i-1] A[i], A[i+1], …, A[m-1]
B[0], B[1], …, B[j-1] B[j], B[j+1], …, B[n-1]

there is two conditions we should make sure:

• len(left_part) == len(right_part)
• max(left_part) <= min(right_part)

so, for the aboving condition, the equivalent should be：

$i + j = m - i + n - j \quad and \quad m \leq n\\ B[j -1] \leq A[i] \quad and \quad A[i - 1] \leq B[j]$

the condition $m \leq n$ means $j \geq 0$

then the median of two arrays is:

the mission can be solved by the following steps:

• find min(len(array1), len(array2)) and set it to m
• searching i in [0, m] to find the ‘i’ that:
• B[j - 1] <= A[i] and A[i -1] <= B[j] where j = (m + n + 1)/2 - i

if the time complexity is $O(log (min(m+n)))$,we should use binary search to find the ‘i’

## Pseudo-code

when it comes to eadge values i=0,i=m,j=0,j=n, where** A[i-1],B[j-1],A[i],B[j]** may not exist.

Author: NYY