SDE理论

发表于 | 更新于 | 评论数：
本文字数： 32k | 阅读时长 ≈ 29 分钟

credit: rick sun

Overview

Data structure is a particular way of organizing data in a computer so that it can be used efficiently.

Common data structure

  • Array
  • Stack
  • Queue
  • Linked List
  • Tree
  • Heap
  • Graph
  • Hash table

Platform

Array and Sorting Algorithms

E.g. int a[10];
Assume a problem’s size is n (n elements).
For example: print all the elements of this array.
Big O notation: algorithm complexity (time complexity, space complexity)
e.g., time complexity O(n).
e.g., space complexity: how much memory does it need to run this algorithm. O(n)
e.g., auxiliary space complexity: is the extra space or temporary space used by an algorithm.

Selection Sort

Example: int[i]=(-1, -3, 4, 7) => (-3, -1, 4, 7) ascending order

  • iteration 1: find global min -3 (-3, -1, 4, 7) insert 3 to the right place
  • iteration 2; find global min in the rest -3 (-1, 4, 7) => -3 -1 (4, 7)
  • iteration 3; find global min in the rest -3 -1 (4, 7) => -3 -1 4 (7)
  • iteration 4; find global min and done .

讲解code要点:
做题要求:
A complete answer will include the following:

  1. Document your assumptions
  2. Explain your approach and how you intend to solve the problem
  3. Provide code comments where applicable
  4. Explain the big-O run time complexity of your solution. Justify your answer.
  5. Identify any additional data structures you used and justify why you used them.
  6. Only provide your best answer to each part of the question.

时间复杂度分析: O(n^2)

Discussion:
1) 什么是面试中一个类型的题?
(1.1) Given an array in Stack1, how to sort the numbers by using additional two stacks?

Stack1 || 1 3 2 4 . global_ min =

Stack2 ||

Stack3 ||
通过Stack1和2选择出最小值放在Stack3中，再将Stack1恢复，循环。
M1: 普通作法，来回倒，s2作为buffer，s3作为output，最后再把s3中排完序的数字倒入s1

(1.2) Follow up, what if only 1 additional stack can be used?

solution: 基于selection sort，一个stack即当buffer又当output，每次倒的时候记录global min及出现次数（以防重复元素）

Merge sort

a[n] = 1,3,5,7,9,8,6,4,2,0
Space = O(n) // look at the pink path
Time = O(nlogn)

Discussion:
1) Could we use Merge Sort to sort a linked list?What is the time complexity if so?
可以，在使用快慢指针找到linked list的中点的时间复杂度为O(N)，所以在横线上的每一层都是O(N)的复杂度，但还是logn层，所以总的复杂度不变，仍为O(n logn)。

2) 什么是面试中一个类型的题?
(2.1) e.g A1B2C3D4 -> ABCD1234
性质:只是combine function的实现稍微不一样而已。 设置成字母比数字小

(2.2) (Advanced topic 1) ABCD1234 -> A1B2C3D4
Way of thinking? How to relate 2.1 and 2.2?
Do not only focus on solving 1 problem and 1 problem only.

(2.3) (Advanced topic 2) K-way merge and its application in Mapreduce
e.g. how to merge TB/PB level data? Algorithm + System Design

(2.4) (Advanced topic 3) count- array problem
Given an array A[N] with all positive integers from [1…N]. How to get an array B[N] such that B[i] represents how many elements A[j] (j > i) in array A[] that are smaller than A[i]. For example, given A[N]={4, 1, 3, 2}, we should get B[N]={3, 0, 1, 0}. Requirement: Time = O(nlogn).
性质: 在log(n)层中，combine function能够让每个element都会和其他所有的元素compare至少一次。总的时间复杂度依然是O(nlogn)

Quick sort

两个挡板 i j, 三个区域 a) b) c) 的思想:

a) [o…i) : i 的左侧(不包含i) 全部为比pivot小的数

b) [i…j] : i 和 j 之间为未知探索区域

c) (j…n-1] : j 的右侧(不包含j)全部为比pivot大或等于的数字

Recursive rule:
Quicksort all numbers to the left of 5,
Quicksort all numbers to the right of 5,

Discussion:
1) What is the worst case scenario for quicksort? Can you provide an example?
O(n^2) 每次的规模减小1个，即每次的pivot选择的都是最小或最大值。所以若对time complexity的bound比 较严格的话选择merge sort会好一些。

2) 什么是面试中一个类型的题?
(2.1) Array Shuffling 1:
Given an array with integers, move all “0s” to the right-end of the array.
(2个挡板，3个区域，相向而行)

(2.2) Character removal from a string: (Will be discussed later in String)
(2个挡板，3个区域，同向而行)
Remove one or more types of characters from a string.

(2.3) Quick Partition Problems
(2个挡板，3个区域，相向而行)

(2.4) Rainbow sort (abcccabbcbbacaa -> aaaaa bbbbb ccccc)
(3个挡板，4个区域，同向 + 相向而行)
Answer:

initialization:
¡= 0; all letters to the left-hand side of are all “a”s
j= 0; (j is actually the current index) all letters in [i, j) are all “b”s ,
k= n-1 (all letters to the right-hand side of k are all “c”s).
unknown area is [j…k]

若j位置是a，则 i, j互换 i++, j++
若j位置是b，则 j++
若j位置是c，则 j, k互换 k—

Discussion:
What did we learn today?

  • Time/Space complexity
  • Sorting Algorithms
    • Time/Space, and why?
    • When to prefer to use one to another?
    • Understand sorting algorithms with design problems?
    • More to do :-)

Recursion I

Recursion 需要掌握的知识点:
1) 表象上: function calls itself
2) 实质上: Boil down a big problem to smaller ones (size n depends on size n-1, or n-2 or…n/2)
3) Implementation上:
a) 1. Base case: smallest problem to solve
b) 2. Recursive rule. how to make the problem smaller (if we can resolve the same problem but with a smaller size, then what is left to do for the current problem size n)
4) to be continued …

Recursion Question 1: Fibonacci sequence
Base case: F(0)= 0; F(1)= 1;
Recursive rule: F(n) = F(n-1) + F(n-2);

Call Stack (Term): was designed to record all local variables that are allocated in the stack.
content:
Level1: n = 4
Level2: n = 3
Level3: n = 2
Level4: n = 1

There are n levels in the recursion tree, and this recursion tree is a binary tree. Thus, there are totally at most O(2^n) nodes in the tree.
Time = O(2^n)
Trick: 所有前面的node的个数的总和，都没有最后一层node的个数多，因此我们分析tree的time complexity,往往只看最后一层node的个数。
Space = O(n) because there are n levels of recursion function call, and thus there are n levels of call stack. In call stack, each level only stores 1 local variable, that is, int n.

Recursion Question 2:
How to calculate a^b (where a is an integer and b is also an integer, we do not care about the corner case where a = 0 or b < 0 for now)
求 2^1000
a=2
b=1000

what is binary search in the context of an array?
1) Array has to be sorted. ascending or descending 1 2 3 5 7 9 … ??????
Not necessarily the case.
2) Problem to solve?

Array 1 3 7 23 57 … 100 99 86 44 32 21 find the maximum
Essentially, the principle of binary search is to reduce the search space by 1/2 of its original size. In the meantime, you must guarantee that the target must not be ruled out.

—- to find an element/number in an array, -> sorted array.
Example: a[7] = 1 2 4 5 7 8 9 whether 4 is in this array or not.

index 0 1 2 3 4 5 6
A[7] 1 2 4 5 7 8 9

Iteration 1: L = 0, R = 6, M = 3 A[M] == A[3] == 5 > target == 4, so R = M-1 = 2;
Iteration 2: L = 0, R = 2, M = 1 A[M] == A[1] == 2 < target == 4, so L = M+1=2;
Iteration 3: L = 2, R = 2, M = 2 A[M] == A[2] == 4 == target , so Done!!!

n element -> time complexity O(log(n));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Classical Version 1.0
// return any target element's index
int binary_search(int a[], int size, int target) {
    int left = 0;
    int right = size - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (a[mid] == target) {
            return mid;
        } else if (a[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 14. Classical Binary Search
// jiuzhang version
public class Solution {
  public int binarySearch(int[] array, int target) {
    // Write your solution here
    if (array == null || array.length == 0) {
      return -1;
    }
    int left = 0, right = array.length - 1;
    while (left + 1 < right) {
      int mid = left + (right - left) / 2;
      if (array[mid] == target) {
        return mid;
      } else if (array[mid] < target) {
        left = mid;
      } else {
        right = mid;
      }
    }
    if (array[left] == target) {
      return left;
    }
    if (array[right] == target) {
      return right;
    }
    return -1;
  }
}

Apply binary search in 2D space
Variant 1.0 application: 2D matrix, sorted on each row, first element of next row is larger (or equal) to the last element of previous row, now giving a target number, returning the position that the target locates within the matrix

1 2 3 4

5 6 7 8 target == 7

9 10 11 12

Solution1:
Step1: Run binary search in the 0-th column to find the possible row that contains target
Step2: Run 2nd binary search, in the particular row to find target (if any)
Time = O(logm + logn) = O(log(m*n))

Solution2:
Run only 1 time of binary search
Left= [0] [0], Right =[m-1]x[n-1], 1D =mxn-1
Mid[row] [col]= (left + right) / 2 = midsize
row= mid size / col;
col = mid_ size % col;
Time = O(log (m*n) )

Variant 1.1 how to find an element in the array that is closest to the target number?
// e.g int a[5] = {1, 2, 3, 8, 9}; target = 4 should return 3
image-20200111011805822
only need to contain the wanted target in the range, not rule out the target number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int binary_search(int a[], int size, int target) {
    int left = 0;
    int right = size - 1;
    
    while (left + 1 < right) { // avoid infinite loop
        int mid = left + (right - left) / 2;
        if (a[mid] == target) {
            return mid;
        } else if (a[mid] > target) {
            right = mid;
        } else {
            left = mid;
        }
    }
    // post-processing
    if (Math.abs(a[left] - target) < Math.abs(a[right] - target)) {
        return left;
    } else {
        return right;
    }
}

其中 line10 right = mid 不能改为 right = mid - 1
其中 line11 left = mid 不能改为 left = mid + 1
反例 [1, 2, 8, 10] target = 3 如果更改了right或left 有可能删掉了想要的index
其中 line5 while 循环条件 start + 1 < end 可以保证循环内 start 和 end 不相邻，从而避免死循环

Variant 1.2 return the index of the first occurrence of an element, say 5

index 0 1 2 3 4 5 6
A[7] 4 5 5 5 5 5 5

Iteration 1: L = 0, R = 6, M = 3 A[M] == A[3] == 5 == target, so R = M = 3;
Iteration 2: L = 0, R = 3, M = 1 A[M] == A[1] == 5 == target, so R = M = 1;
因为左右边界相邻，我们 terminate binary search，再做 post processing.

Variant 1.3 return the index of the last occurrence of an element
e.g. inta[6] = [4, 5, 5, 5, 5, 5];
if target == 5; then index 5 is returned;
if target == 10; then -1 is returned;

Variant 1.4 how to find closest k elements in the array that is closest to the target number?
e.g int a[5] = {1, 2, 3, 8, 9}; Target == 4;
k = 3, solu = {3, 2, 1}
Solution:
Step1: we first move L and R by using binary search to make it close to the target number, until there are two or less elements in between L and R.
Step2: 谁小移谁
Time = O(logn+ k)

Variant 1.5 how to find the smallest element that is larger than a target number?

Binary Search Variant 2.0:
Important Question: Given a sorted dictionary with unknown size, how to determine whether a word is in this dictionary or not.
Example: dictionary[x] = { 1 3 5 7 9 ….. 100 …. 1000000000 ….. }
Target == 9999
assumption if dictionary[index] == NULL then we know the size of dictionary is < index;
Step1 jump out step = 2
Step2 jump out step = 2^2 = 4
Step3 jump out step = 2^3 = 8
Step4 jump out step = 2^4 = 16
Stepk until dictionary[2^k] >= target OR dictionary[2^k] == null
// target can exist and its 2^(k-1) < index < 2^k

Further discussion about binary search:
Why not jump step = jump step 10, instead of jump step = jump step 2

10Times: log_10 (n) + log_2 (10n)
2 Times: log_2 (n) + log_2 (2n)
比较10 times - 2 times即可

Discussion When to use binary search
1) very very classical problem: when the input is completely/partially sorted
a. sorted array
b. sorted array but shifted
C. two sorted order array but
Array 1 3 7 23 57 …. 100 99 86 44 32 21
2) has some logic rule under the hood. but you can figure out proof that you can disregard 1/2 searching range each time
ARRAY 1 XXXXXXXXXXXXXXXXXXX m
ARRAY 2 YYYYYYYYYYYYYYYY n
(m+n)/2 no no no!!!!
FIND THE K-th smallest element in the array
Yes: reduce the search range from k to k/2

Queue & Stack

Queue
1.1. Example: wait in a line, FIFO == First in first out
1.2. Usages: Breadth-First Search related problems
1.3. C++ reference http://www.cplusplus.com/reference/queue/queue/
1.4. 典型问题
1.4.1. Tree print out by level
1.4.2. Sliding window problems (Deque: double ends manipulation)

poll() — take the element from head
peek() — look at the element at the head
offer() — insert the element at the tail

Stack
LIFO Last in first out: like a box
e.g. insertion order 1.2.3.4, then in the stack, it looks like
5 <- top of the stack. All operations can only be done to this element
4
3
2
1 <- bottom of the stack
All operations available: push(), pop(), top()
Implementation: popular data structure: array or vector

Four popular interview questions:
Question 1: How could we implement a queue by using two stacks?
           head                             tail
           1 2 3 4 lI        II 5 6 7 8 9
                stack1        stack2

stack 1 -> responsible for poll() -> stack1.pop()
stack 2 -> responsible for offer() -> stack2.push()

case1. if stack1 is not empty, stack1.pop()
case2. if stack2 is empty -> pop elements from stack2 and push them into stack1

Time Complexity:
offer() - O(1)
poll() - worst case - case2 O(n)
Amortized Analysis:
for the n elements:
for the first element - worst case (2n + 1) pop all from stack2 and push all into the stack 1 and pop 1 element from stack1
for the following n-1 elements - 1 * (n-1)

total 2n + 1 + n - 1 = 3n
O(3n)/n = O(3) = O(1) — Amortized Time Complexity.

Question 2: How to implement the min() function when using stack with time complexity O(1);
stack1 II 5 4 3 4 5
stack2 II 5 4 3 3 3
stack2: maintain the corresponding min value according to stack1.

Follow up Question: how to optimize the space when there are a lot of duplicate elements in stack1?stack1 II 5 4 3 3 3 3 3 3 3 3 3
stack2 II 5 4 3 3 3 3 3 3 3 3 3

stack1 II 5 4 3 3 3 3 3 3 3 3 3
stack2 II <5, 0> <4, 1> <3, 2>

1
2
3
4
class Wrapper {
    int min;
    int pos;
}

pop only when -> stack1.size() == stack2.peek().pos + 1

Question 3: How to sort numbers with two stacks
stack1 II 1 2 2 2 4 3
stack2 II 1
stack2 to maintain the numbers in sorted order.
two variable: globalMin and counter
while (stack2.top() >= globalMin) {

}

laicode 280.

Question 4: How to use multiple stacks to implement a de-queue(double ended queue)
           head                             tail
           1 2 3 4 lI        II 5 6 7 8 9
                stack1        stack2

pushL stack1.push()
pushR stack2.push()

popL
case1: stack1 is not empty, O(1)
case2: if stack1 is empty, we need to pop all the elements from stack2 and push them to stack1
popR
case1: stack2 is not empty, O(1)
case2: if stack2 is empty, we need to pop all the elements from stack1 and push them to stack2

Worst case: amortized Time Complexity O(n)
e.g. stack1: empty stack2: empty
pushR(5, 6, 7, 8, 9) - n elements
popL - n
popR - n-1
popL - n-2
popR - n-3
……
Total: O(n + n-1 + n-2 + … + 1) = O(n^2), O(n^2) / n = O(n)

How to optimize to O(1)?
分析复杂度高的原因是每次都将所有元素移动，如果借助一个辅助栈只移动一半元素，时间平摊到其他操作则会大幅度降低复杂度。
intuition: move half of the elements in stack2 to stack1.
第一次操作：
stack2移动一半元素到stack3 O(n)
stack2移动剩余一半元素到stack1 O(n)
stack3移动回元素到stack2 O(n)
0.5n个元素其余次操作: O(1)
amortized Time Complexity: ( O(n) + O(n) + O(n) + O(0.5n) ) / 0.5n = O(7) = O(1)

Discussion: 什么问题要往Stack上考虑?
从左到右linear scan一个array/string时, 如果要不断回头看左边最新的元素时往往要用到stack
1) Histogram中找最大的长方形
2) reverse polish notation逆波兰表达式的计算a (b+c) → abc+
3) String的repeatedly deduplication. cabba → caa → c

LinkedList

Key points:
1) When you want to de-reference a ListNode, make sure it is not a NULL pointer
2) Never ever lost the control of the head pointer of the LinkedList

Question: How to reverse a linked list?
Node1(head) —> Node2 —> Node3 —> Node4 …. —> NodeN —> NULL
reversed: NULL <— Node1<— Node2 <— Node3 <— …. <— NodeN( head)

Iterative Solution:

1
2
3
4
5
6
7
8
9
10
11
12
// Solution1: create a new linked list
public ListNode reverse(ListNode head) {
    ListNode newHead = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = newHead;
        newHead = cur;
        cur = next;
    }
    return newHead;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Solution2: 原地反转指针指向
public ListNode reverse(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode next = head.next;
    head.next = null;
    while (next != null) {
        ListNode cur = next;
        next = next.next;
        cur.next = head;
        head = cur;
    }
    return head;
}

Recursive Solution:
image-20200111180526943

1
2
3
4
5
6
7
8
9
// Recursive way:
public ListNode reverseLinkedList(ListNode head) {
    if (head == NULL || head.next == NULL) return head; // base case
    ListNode newHead = reverseList(head.next);
    // breaking point..
    head.next.next = head;
    head.next = null;
    return newHead;
}

常见考题:
Q1. How to find the middle node of a linked list?
快慢指针 偶数个节点选左边的那个，因为左边的next node就是右边的。
Q2. 用快慢指针判定一个linkedlist是否有环。
Q3. Insert a node in a sorted linked list (simple)
N1 < node < N2 找到N1和N2
Q4. How to merge two sorted linked list into one long sorted linked list
有可能插头或插尾，处理corner case使用dummy node
image-20200111183507719
step 1: find mid node
step 2: reverse the second half list
step 3: merge two sub lists.

Q6. Partition List:
Given a linked list and a value x, partition it such that all nodes less than x come first, then all nodes with value equal to x or greater than or equal to x. The original relative order of the nodes in each of the two partitions should be preserved.
For example,
Input: 1 -> 6 -> 3 -> 2a -> 5 -> 2b and target x = 4,
result: 1 -> 3 -> 2a -> 2b -> 6 -> 5.

Solution:
Step1: allocate two new linked list heads;
Step2: Iterate over every single element in the list, and compare with the current node’s value with the target’s value.
Case1 if current.value < target.value: Add the current node to the tail of the first linked list .
Case2: otherwise, add the current node to the tail of the second linked list.
1st half (small values )
2nd half (large values )
Step3: Concatenate the tail of the first half to the head of the 2nd linked list.
Step4: The tail of the large list.next == NULL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class PartitionLinkedList {
	public ListNode partition (ListNode head, int x) {
 		if (head == null) return null;
        ListNode fakeHeadSmall = new ListNode(0); 
        ListNode fakeHeadLarge = new ListNode(0); 
        ListNode smallTail = fakeHeadSmall; 
        ListNode largeTail = fakeHeadLarge; 
        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                smallTail.next = current;
                smallTail = current;
            } else {
                largeTail.next = current;
                largeTail = current;
            }
            current = current.next;
        }
        largeTail.next = null; // terminate the list with null
        smallTail.next = fakeHeadLarge.next;
        return fakeHeadSmall.next;
    }
}

Binary Tree & Binary Search Tree

Definition: at most two children node.

Example:

Trick: base case usually refers to the null ChildNode below the leaf node.

基本概念

  • Balanced binary tree: is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less.
  • Complete binary tree: is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
  • Binary Search tree: for every node in the tree, the values in its left subtree are all smaller than its value, and the values in its right subtree are all larger than its value.

Discussion (High Level)

  • Binary tree往往是最常见的，和recursion 结合最紧密的面试题目类型。
  • Reasons:
    • 每层的node具备的性质，传递的值和下一层的性质往往一致。比较容易定义recursive rule.
    • Base case (generally): null pointer under the leaf node
    • Example1: int getHeight (Node root)
    • Example2: 统计tree里边有多少个node?
  • Fundamental Knowledge:
    • Traversal of a binary tree
    • Definition
      • Balanced binary tree
      • Complete binary tree
      • Binary search tree (BST)

Binary Tree

Q1. Get height of a binary tree

1
2
3
4
5
6
public int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return 1 + Math.max(getHeight(root.left), getHeight(root.right));
}

Time = O(n) where n is the total number of the nodes
Space = O(n) == O(height)

Q2. How to determine whether a binary tree is a balanced binary tree?

1
2
3
4
5
6
7
8
9
10
11
public boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return false;
    }
    return isBalanced(root.left) && isBalanced(root.right);
}

image-20200114205944605

Q3. How to judge whether a binary tree is symmetric?

1
2
3
4
5
6
7
8
9
10
public boolean isSymmetric (TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    } else if (left == null || right == null) {
        return false;
    } else if (left.value != right.value) {
        return false;
    }
    return isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
}

Time = O(n)
Space = O(n)

Q3. Let’s assume if we tweak the Ichild with rchild of an arbitrary node in a binary tree, then the
“structure” of the tree are not changed. Then how can we determine whether two binary trees’
structures are identical.

1
2
3
4
5
6
7
8
9
10
11
public boolean isIdentical (TreeNode left, TreeNode right) {
    if (left == null && right == null) {
        return true;
    } else if (left == null || right == null) {
        return false;
    } else if (left.value != right.value) {
        return false;
    }
    return isIdentical(left.left, right.left) && isIdentical(left.right, right.right) 
        || isIdentical(left.left, right.right) && isIdentical(left.right, right.left);
}

image-20200114213236663

Total number of nodes in this quad tree = 4^(log2(n)) = 2^(2log2(n)) = O(n^2)

Binary Search Tree

Q1. How to determine a binary tree is a BST?

1
2
3
4
5
6
7
8
9
10
public boolean isBSTHelper(TreeNode root, int min, int max) {
    if (root == null) {
        return true;
    }
    if(root.val <= min || root.val >= max) {
        return false;
    }
    return isBSTHelper(root.left, min, root.val) 
        && isBSTHelper(root.right, root.val, max);
}

Time = O(n)
Space = O(height) = O(n)

Discussion
Recursion在tree题目的基本应用大致分为2类用法（存疑）

  1. 把value从上往下传递(then从下往上)的题目
    • BST判定方法
  2. 把value从下往上传递(更为常见，必须熟练掌握)
    • getHeight(TreeNode root) 是经典的把integer value从下往上传递的题
    • isBalanced(TreeNode root)是把boolean value从下往上传递的题目
    • isSymmetric(TreeNode root1, TreeNode root2)是把boolean value从下往上传递的题目
    • Assign the value of each node to be the total number of nodes that belong to its left subtree. (是把integer value从下往上传递的题目)

Q2. Print BST keys in the given range
Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all the keys of tree in range k1 to k2. i.e. print all x such that k1 <= x <=k2 and x is a key of given BST. Print all the keys in an increasing order.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void rangeInOrder(TreeNode root, int k1, int k2) {
    if (root == null) {
        return;
    }
    if (root.value > k1) {
        rangeInOrder(root.left, k1, k2);
    }
    if (root.value >= k1 && root.value <= k2) {
        System.out.println(root.value);
    }
    if (root.value < k2) {
        rangeInOrder(root.right, k1, k2);
    }
}

Heap

堆 (英语: heap) 亦被称为: 优先队列 (英语: priority queue)
Example

index 0 1 2 3 4 5
value 1 3 2 5 4 7

Heap: is an unsorted array but have special rules to follow
性质: 堆的实现通过构造二叉堆(binary heap), 这种数据结构具有以下性质

  1. 任意节点小于它的所有后裔，最小元素在堆的根上(堆序性)。
  2. 堆总是一棵完全树。complete tree
  3. 将根节点最大的堆叫做MAX HEAP，根节点最小的堆叫做最小堆MIN HEAP
  4. index of lChild = index of parent X 2 + 1
  5. index of rChild = index of parent X 2 + 2
  6. unsorted but follow rules above

支持的基本操作

  1. insert: 向堆中插入一个新元素；时间复杂度O(log(n))
  2. update: 将新元素提升使其符合堆的性质；时间复杂度O(log(n))
  3. get/top: 获取当前堆顶元素的值；时间复杂度O(1)
  4. pop: 删除堆顶元素；时间复杂度O(log(n))
  5. heapify: 使得一个unsorted array变成一个堆。时间复杂度O(n)

经典考题
Q1 Find smallest k elements from an unsorted array of size n.

  • Solution1:
    sort it and return the first k element!
    Time = O(nlogn)

  • Solution2:
    e.g. k= 3,
    Use selection sort principle
    1st iteration to find 1st smallest element to return
    2nd iteration to find 2nd smallest element to return
    …
    k-th iteration to find the k-th smallest
    Time = O(k * n)

  • Solution3: MIN-HEAP of size n
    Step1: heapify the whole array to make it a MIN-heap. O(n)
    Step2: keep popping k times k*log(n)
    Total time = O(n) + O(klog(n))

  • Solution4: MAX-HEAP of size k
    xxxxxx Yxxxxxxxxxxxxxxxxxxxx
    size= k k+1
    Step1: insert all first k elements into a max-heap (optimization heapify first k element) O(k)
    Step2: from the k+1-th element to the n-th element,
    if the current element Y

    • case2.1 Y < max-heap.top(), we call max-heap.pop(), and then max-heap.insert(Y)

    • case2.2 Y >= max-heap.top(), do nothing.

      Time = O(k) + O((n-k) * log(k)

COMPARISON:3, 4 MIN-HEAP MAX-HEAP
Time Complexity O(n) + O(klog(n)) O(k) + O((n-k) * log(k)
Case1 k <<< n O(n) O(n) * log(k) hard to say
Case2 k~n O(nlogn) O(nlogn) hard to say
  • Solution5: average time = O(n)image-20200113185237022on average= on average = O(n + n/2 + n/4 + n/8+ 1…) = O(n)
    worst case = O(n^2)

Graph Search Algorithms I

image-20200113190008687

  1. Node / State
  2. Edge / action
  3. Directed vs undirected graph
  4. Representation of the graph
  • Adjacency Matrix
    image-20200113190636591
    Pros: Representation is easy to implement. Edge removal takes O(1) time. Queries like whether
    there is an edge from vertex ‘u’ to vertex ‘V’ are efficient and can be done O(1).
  • Adjacency List
    image-20200113190814356
    Vertices/nodes: IVI
    Edges: IEI
    Pros: Space complexity= O(lVI+lEl) . Adding a vertex/node to the graph is easier.
    Cons: Time complexity is O(V) to check whether there is an edge from a node to the other.
    (compared to O(1) in adjacent matrix)
  • Use a hash_table
    >
    image-20200113191319407

图里常用的search算法

Breadth-First Search (BFS-1):


print/visit = 1 32 547 9 11

How to describe a relatively complex algorithm:

  1. what kind of data structure that this algorithm uses
    queue
  2. what are the actions of this algorithm step by step
    • initial state: insert the start node into the queue queue = {1}
    • process: while the queue is not empty, pop the left-most element out of the queue and expand it, generate all its successors and insert all of them into the tail of the queue
    • termination condition: when the queue is empty

经典例题1：分层打印一个binary tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// param: root - the root of the tree
public void BFS(Node root) {
    if (root == null) {
        return;
    }
    Queue<Node> q = new LinkedList<Node>();
    q.offer(root);
    while(!q.empty()) {
        int size = q.size(); // size = # of generated nodes in the next layer.
        for (int i = 0; i < size; i++) {
            Node n = q.remove();
            if (n.left != null) {
                q.offer(n.left);
            }
            if (n.right != null) {
                q.offer(n.right);
            }
            System.out.print(n.val + " ");
        }
        System.out.println();
    }
}

经典例题2: Bipartite : whether a graph’s node can be divided into two group, such that the nodes in each group do not have direct edges between the nodes that belong to the same group.

1 —- 2 —- 4
\ /
3

queue= {2, 3}

expand 1 (red) —> generate 2 and 3

expand 2 —> generate all the neighbors of 2

  • case 1: if the neighbor has not been colored (e.g., 4) => just color it with the other color
  • case 2: if the neighbor has the other color than mine (e.g., 1) => ignore
  • case 3: if the neighbor has the same color as mine (e.g., 3) => return false
1
2
3
4
5
class GraphNode {
    int value;
    char set; // u or v?
    ArrayList<GraphNode> succesors;
}

经典例题3: Determine whether a binary tree is a complete binary tree

Solution: after detecting the first node that misses one child, then check if all following
nodes expanded have any node generated (if any, then false)

Discussion: When to consider to use BFS?

  1. When we want to deal with the node relationship in the same level
  2. (Common mistake): BFS1 is NOT the right algorithm to find the shortest path from point A to point B in an arbitrary graph (cost might not be the same).
    • if the edge costs in the graph are all the same (= uniform) then BFS1 can find the
      shortest path.

Best First Search (BFS-2)

经典算法: Dijkstra’s Algorithm (runtime efficiency improvement: A * algorithm)

  1. Usages: Find the shortest path from a single node (source node) to any other
    nodes in that graph (点到面(==所有点)的最短距离算法)/

  2. Example problem: 从北京到中国其他所有主要城市的最短距离是多少

  3. Data structure: priority_queue (MIN_HEAP)

  4. 解题思路
    4.1 Initial state (start node)

    4.2 Node expansion/Generation rule:

    4.3 Termination condition: 所有点都计算完毕才停止，也就是p_ queue变空

  5. Example

    image-20200113195544938

  • initial state: no nodes have been expanded, p_queue = {node(4,0)}
  • process: p_queue.pop(), pop node(4,0) out of the p_queue, expand node(4,0) generate three successors: node(5,10), node(3,1), node(6,1), p_queue = {node(5,10), node(3,1), node(6,1)}
  • tie breaking strategy: random
    pop node(6,1) generate nothing, p_queue = {node(5,10), node(3,1)}
  • pop node(3,1) generate node(2, cost == parent cost + 1) = (2,2), p_queue = {node(5,10), node(2,2)}
  • pop node(2,2) generate node(5, 2+1) and node(1,2+1), p_queue = {node(5,3), node(1,3)}
  • pop node(5,3), p_queue = {node(1,3)}
  • pop node(1,3), p_queue = {}
  • terminate
  1. properties
  • one node can be expanded once and only once
  • one node can be generated more than once. (cost can be reduced over time)
  • all the cost of the nodes that are expanded are monotonically non-decreasing (所
    有从priority queue里面pop出来的元素的值是单调非递减 -> 单调递增)
  • time complexity, for a graph with n node is O(nlogn)
  • when a node is popped out for expansion, its value is fixed which is equal to the shortest distance from the start node.

经典考题: (运用Dijkstra’s Algorithm的性质)
Given a matrix of size NxN, and for each row the elements are sorted in an ascending order, and for each column the elements are also sorted in an ascending order. How to find the k-th smallest element in it?

image-20200113211643029

Solution:

  1. Initial state: start node = [0] [0]
  2. Node expansion/ generation rule: expand [i] [j] generate [i] [j+1] and [i+1] [j]
  3. Termination condition: when the k-th element is popped out of the p-queue

Analysis: there are totally k nodes to be popped out of the p-queue (= k iterations)
for each iteration

  • pop 1 element out of the p-queue (p-queue size < 2k)
    time = log(2k)

  • generate 2 elements and insert them into the p-queue
    time = 2log(2k)

  • Total time for each iteration = 3log(2k)
    Since there are k iterations, the total time = k * 3log(2k) = 3k(log2k) = k log(k)

    image-20200113213713121

1 2a 2b 3a 3b 3b 3c 4
k= 7 your solution return 3c, correct answer should be 4.
The reason is due to the fact that 3b was generated twice!

Our question is how to de-duplicate 3b 3b?

  • method1: we can use a hash_ set >
  • method2: use another 2D matrix to save if a node is visited or not

Graph Search Algorithms II (DFS)

image-20200227214109152

Hash table

image-20200227215141422

String I

image-20200227215830965

String II

image-20200227220624305

Recursion II

image-20200227221324735

Dynamic Programming I

image-20200228013638237

Dynamic Programming II

image-20200228013825791

Probability, Sampling, Randomization, etc.

image-20200228014427275

Recursion III

Q1. Tree + Recursion 第一类问题:
Use recursion to return values in a bottom-up way in binary tree

Q1.1 Determine whether a binary tree is a balanced binary tree (O(nlogn) solution).
What’s the definition of “balanced”? It could be:

  • the tree has a minimum possible overall height

  • no leaf is too further away. i.e. 0 or 1, from root to any other leaf

  • left and right sub-tree have similar height, i.e. difference is 0 or 1 (balanced height)

(1) 旧的解法 O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
public boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }
    int leftHeight = getHeight(root.left);
    int rightHeight = getHeight(root.right);
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return false;
    }
    return isBalanced(root.left) && isBalanced(root.right);
}

Q1.2 Determine whether a binary tree is a balanced binary tree (O(n) solution). 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean isBalanced(TreeNode root) {
    int result = getHeight(root);
    if (result > 0) {
        return true;
    } else {
        return false;
    }
}

// helper
public int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = getHeight(root.left);  // step 1
    int rightHeight = getHeight(root.right);
    
    if (leftHeight == -1 || rightHeight == -1 || 
        Math.abs(leftHeight - rightHeight) > 1) {  // step 2
        return -1;
    }
    return Math.max(leftHeight, rightHeight) + 1;  // step 3
}

Q1.3 Given a binary tree in which each node element contains a number. Find the maximum possible sum from one leaf node to another.
The maximum sum path may or may not go through root. For example, in the following tree, the maximum sum is 27( 3 + 6 + 9 + 0 - 1 + 10). Expected time complexity is O(n).

image-20200214140336426

Way of thinking (Tricks)

  1. What do you expect from your lchild / rchild ?
    Max single path in my left subtree (1)
    Max single path in my right subtree (2)
  2. What do you want to do in the current layer ?
    update global_max = left + right + root.value if feasible
  3. What do you want to report to your parent ?
    it is usually the return type of the recursion function
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
    maxPath(root);
    return max;
}

public int maxPath(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int left = maxPath(root.left);
    int right = maxPath(root.right);
    if (root.left != null && root.right != null) {
        max = Math.max(max, root.key + left + right);
        return Math.max(left, right) + root.key;
    }
    return root.left == null ? root.key + right : root.key + left;

}

Q1.4 (人字形Path问题)
Get Maximum sum of the path cost from any node to any node (not necessarily from leaf to leaf).

Way of thinking (Tricks)

  1. What do you expect from your lchild / rchild ?
    Max single path in my left subtree (ended at the left child node) If this value is negative, we discard it
    Max single path in my right subtree (ended at the right child node) If this value is negative, we discard it
  2. What do you want to do in the current layer ?
    update global_max = left + right + root.value if feasible
  3. What do you want to report to your parent ?
    it is usually the return type of the recursion function
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class MaximumPathSumBinaryTree2 {

	private int max = Integer.MIN_VALUE;
	
	public int maxPathSum(TreeNode root) {
		helper(root);
		return max;
	}

	private int helper(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int left = helper(root.left);
		int right = helper(root.right);
		left = left < 0 ? 0 : left;
		right = right < 0 ? 0 : right;
		max = Math.max(max, root.key + left + right);
		return root.key + Math.max(left, right);
	}
	
	// Time complexity is O(n).
	// Space complexity is O(n), because of call-stack, if the binary tree is highly unbalanced.
}

Q2. Tree + Recursion 第二类问题: (Path Problem in binary tree)

Discussion:
Note that: Tree相关问题，路径种类可以分为两大类

Class 1: 人字形path，这类题一般需要从下往上传integer value (E.g., Q1.1 - 1.4 above)

Class 2: 从root往下（直上直下）path
Key point: carry a 直上直下 path prefix（非人字形）while traversing the tree:

​ a. complete path from leaf to root
​ b. sub-section of complete path from leaf to root

​ 10
​ / \
​ -2 7
/ \
8 -4

Prefix_of_path = {10, -2, -4}

Q2.1 Given a binary tree in which each node contains an integer number. Find the maximum possible sub-path sum from root node to leaf node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Assumption: root != null

public class MaximumPathSumBinaryTree4 {

	public int maxPathSum(TreeNode root) {
		if (root.left == null && root.right == null) {
			return root.key;
		}
		int left = (root.left == null) ? 0 : maxPathSum(root.left);
		int right = (root.right == null) ? 0 : maxPathSum(root.right);
		return root.key + Math.max(left, right);
	}

	// Time complexity is O(n).
	// Space complexity is O(n), if the binary tree is highly unbalanced.
}
1
2
3
4
5
6
7
8
9
10
11
12
void maxPath(TreeNode* root, int sum, int& globalMax) {
    if (root == NULL) {
        return;   // base case 1
    }
    if (root->left == NULL && root->right == NULL) {
        globalMax = max(sum + root->val, globalMax);
        return;   // base case 2
    }
    
    maxPath(root->left, sum + root->val, globalMax); // go left
    maxPath(root->right, sum + root->val, globalMax);// go right
}

Q2.2 Given a binary tree in which each node contains an integer number. Determine if there exists a path (the path can only be from one node to itself or to any of its descendants), the sum of the numbers on the path is the given target number.

recursion function + dp past prefix trick

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.HashSet;
import java.util.Set;

public class BinaryTreePathSumToTarget3 {
	
	public boolean exist(TreeNode root, int target) {
		if (root == null) {
			return false;
		}
		Set<Integer> prefixSums = new HashSet<>();
		prefixSums.add(0);
		return DFS(root, target, 0, prefixSums);
	}

	private boolean DFS(TreeNode root, int target, int prefixSum, 
                        Set<Integer> prefixSums) {
		prefixSum += root.key;
		if (prefixSums.contains(prefixSum - target)) {
			return true;
		}
		// add
		boolean needRemove = prefixSums.add(prefixSum);
		// dfs
		if (root.left != null && DFS(root.left, target, prefixSum, prefixSums)) {
			return true;
		}
		if (root.right != null && DFS(root.right, target, prefixSum, prefixSums)) {
			return true;
		}
		// remove
		if (needRemove) {
			prefixSums.remove(prefixSum);
		}
		return false;
	}

	// Time complexity is O(n).
	// Space complexity is O(n), if binary tree is highly unbalanced 
}

那个remove的标记逻辑是这样的，

1） 如果加的prevsum不在集合中存在，就是true，也好理解，就是你如果当前节点探索完了，你就回到父亲节点，刚才的prevsum值应该无效了，因为set中保留的是相对当前考察节点有意义的累加值集合，就是它上边一直到根节点的所有可能累加值。删掉的是刚才子节点对应的prevsum。

2）而如果prevsum的值已经出现过，那说明不是因为当前的prevsum插入导致的，而是直到根节点的路径上某个节点导致的，这样就不应该删，那个数还有用。

比如：

​ 4
​ / \
​ 2 -3
​ / \
​ 4 2
​ /
​ -4

处理到-3，prevsum应该是4+(-3)=1 此时1在返回前删
处理到-4，prevsum应该是4+(-3)+4+(-4)=1 此时1在递归返回前不删

带这个逻辑的递归保证了只在第一次出现那个数的地方删。

Q2.3 Given a binary tree in which each node contains an integer number. Find the maximum possible sub-path sum (both the starting and ending node of the sub-path should be on the same path from root to one of the leaf nodes, and the sub-path is allowed to contain only one node).

DP solution: 从上往下的 max subarray sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// sum represents [from the root node to the current node] the largest sum of the path prefix (must including the current node)
public class Solution {
  public int maxPathSum(TreeNode root) {
    // Write your solution here
    int[] max = {Integer.MIN_VALUE};
    int sum = Integer.MIN_VALUE;
    helper(root, max, sum);
    return max[0];
  }
  public void helper(TreeNode root, int[] max, int sum) {
    if (root == null) {
      return;
    }
    if (sum < 0) {
      sum = root.key;
    } else {
      sum += root.key;
    }
    max[0] = Math.max(max[0], sum);
    helper(root.left, max, sum);
    helper(root.right, max, sum);
  }
}

从下往上的 max subarray sum

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class MaximumPathSumBinaryTree3 {

	private int max = Integer.MIN_VALUE;
	
	public int maxPathSum(TreeNode root) {
		helper(root);
		return max;
	}

	private int helper(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int left = helper(root.left);
		int right = helper(root.right);
		left = left < 0 ? 0 : left;
		right = right < 0 ? 0 : right;
		max = Math.max(max, root.key + Math.max(left, right));
		return root.key + Math.max(left, right);
	}

	// Time complexity is O(n).
	// Space complexity is O(n), because of call-stack, if the binary tree is
	// highly unbalanced.
}

Q3. Tree + Recursion 第三类问题: Tree Serialization Problem

Q3.1 Given a binary tree, convert it to a doubly linked list with its in-order sequence.

Key Points:

  1. When traverse to a current node, we need to know which node was the previous node
  2. Never ever lost the control over the new head. (We need to return the new Head)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class BinaryTreeToDoublyLinkedList {

	static Node prev = null;

	public Node convert(Node root) {
		Node[] head = new Node[] { null };
		helper(root, head);
		return head[0];
	}

    private void helper(Node root, Node[] head) {
        // base case
        if (root == null) {
            return;
        }
        helper(root.left, head);
        if (prev == null) { // initially
            head[0] = root;
        } else {
            root.left = prev;
            prev.right = root;
        }
        prev = root;
        helper(root.right, head);
    }
}

Find the node with max different JAVA 答案的疑问
闫老师在存node和max different的时候，实用数组来储存的，node[0]和diff[0]。想请教下闫老师处于什么考虑用数组来存这两个值，而不用单个一个TreeNode node 和 int diff来存？

这个是pass by value和pass by reference的区别。
java passes the object reference ‘by value’. When an object is passed as argument to a method, actually the reference to that object is passed. The formal parameter is a mapping of the reference to the actual.
体会下下面两个的区别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void foo1(int diff) {
	diff = 2;
}

public static void foo2(int[] diff) {
	diff[0] = 2;
}

public static void main(String[] args) {
	int a = 0;
	int[] b = {0};
	foo1(a);
	foo2(b);
	System.out.println(a);
	System.out.println(b[0]);
}

Q4. Tree + Recursion 第四类问题: Tree De-serialization Problem

Discussion:

Reconstruct a tree by using xxx-order and in-order traversal sequences

此类问题的要点是把global的问题一分为二 (recursively), 每半边返回一个subtree的root node.

Recursion 需要掌握的知识点:

1) 表象上: function calls itself
2) 实质上: Boil down a big problem to smaller ones (size n depends on size n-1, or n-2 or…n/2)
3) Implementation上:
a) 1. Base case: smallest problem to solve
b) 2. Recursive rule. how to make the problem smaller (if we can resolve the same problem but with a smaller size, then what is left to do for the current problem size n)
4) In more details (Recursive Function Signature must keep the same logic)

Q4.1 Given the pre-order and in-order traversal sequence of a binary tree, reconstruct the original tree.

​ 10
​ / \
​ 5 15
​ / \ / \
​ 2 7 12 20

Index: 0 1 2 3 4 5 6
Preorder: 10 5 2 7 15 12 20
Inorder: 2 5 7 10 12 15 20 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
  	public TreeNode reconstruct(int[] inorder, int[] preorder) {
		Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return helper(preorder, inorder, 0, inorder.length - 1, 0, preorder.length - 1, map);       
    }
	private TreeNode helper(int[] preorder, int[] inorder, int inL, int inR, int preL, int preR, Map<Integer, Integer> map) {
        //base case
        if(inL > inR) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preL]);
        int size = map.get(preorder[preL]) - inL;
        root.left = helper(preorder, inorder, inL, inL + size - 1, preL + 1, preL + size, map);
        root.right = helper(preorder, inorder, inL + size + 1, inR, preL + 1 + size, preR, map);
        return root;     
    }
}

Q4.2 Given the postorder and inorder traversal sequence of a binary tree, reconstruct the original tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.HashMap;
import java.util.Map;

// Assumption:
// 1. The given sequences are not null and they have the same length
// 2. There are no duplicate keys in the binary tree

public class ReconstructBinaryTreeWithPostorderAndInorder {

	public TreeNode reconstruct(int[] in, int[] post) {
		Map<Integer, Integer> map = indexMap(in);
		return helper(post, map, 0, in.length - 1, 0, post.length - 1);
	}

	private Map<Integer, Integer> indexMap(int[] in) {
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < in.length; i++) {
			map.put(in[i], i);
		}
		return map;
	}

	private TreeNode helper(int[] post, Map<Integer, Integer> map, int inLeft, int inRight, int postLeft,
			int postRight) {
		if (inLeft > inRight) {
			return null;
		}
		TreeNode root = new TreeNode(post[postRight]);
		int inMid = map.get(root.key);
		root.left = helper(post, map, inLeft, inMid - 1, postLeft, postLeft + inMid - inLeft - 1);
		root.right = helper(post, map, inMid + 1, inRight, postLeft + inMid - inLeft, postRight - 1);
		return root;
	}

	// Time complexity is O(n).
	// Space complexity is O(n).
}

Q4.3 Given the levelorder and inorder traversal sequence of a binary tree, reconstruct the original tree.

​ 20
​ / \
​ 8 22
​ / \
​ 4 12
​ / \
​ 10 14

Index: 0 1 2 3 4 5 6
In-order: 4 8 10 12 14 20 22
Level-order: 20 8 22 4 12 10 14

20 index in in-order 5

Level-order left = {8, 4, 12, 10, 14}
Level-order right = {22}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// Given the levelorder and inorder traversal sequence of a binary tree, reconstruct the original tree.

// Assumption:
// 1. The given sequences are not null and they have the same length
// 2. There are no duplicate keys in the binary tree

public class ReconstructBinaryTreeWithLevelorderAndInorder {

	public TreeNode reconstruct(int[] in, int[] level) {
		Map<Integer, Integer> map = indexMap(in);
		List<Integer> list = new ArrayList<>();
		for (int i : level) {
			list.add(i);
		}
		return helper(map, list);
	}

	private Map<Integer, Integer> indexMap(int[] in) {
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < in.length; i++) {
			map.put(in[i], i);
		}
		return map;
	}

	private TreeNode helper(Map<Integer, Integer> map, List<Integer> list) {
		// base case
		if (list.isEmpty()) {
			return null;
		}
		TreeNode root = new TreeNode(list.get(0));
		List<Integer> left = new ArrayList<>();
		List<Integer> right = new ArrayList<>();
		for (int i : list) {
			if (map.get(i) < map.get(root.key)) {
				left.add(i);
			} else if (map.get(i) > map.get(root.key)) {
				right.add(i);
			}
		}
		root.left = helper(map, left);
		root.right = helper(map, right);
		return root;
	}

	// Time complexity is O(n^2) in the worst case, but O(n*log(n)) in the
	// average case.
	// Space complexity is O(n).
}

Q4.4 Construct a BST tree from Pre-order traversal only.

​ 10
​ / \
​ 5 15
​ / \ / \
​ 2 7 12 20

Index: 0 1 2 3 4 5 6
Preorder: 10 5 2 7 15 12 20

​ 10
​ ?L ?R
​ smaller than 10 bigger than 10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Assumption:
// 1. The given sequence is not null
// 2. There are no duplicate keys in the binary search tree

public class ReconstructBSTWithPreorder {

	public TreeNode reconstruct(int[] pre) {
		int[] index = new int[] { 0 };
		return helper(pre, index, Integer.MAX_VALUE);
	}

	private TreeNode helper(int[] pre, int[] index, int max) {
		if (index[0] >= pre.length || pre[index[0]] > max) {
			return null;
		}
		TreeNode root = new TreeNode(pre[index[0]++]);
		root.left = helper(pre, index, root.key);
		root.right = helper(pre, index, max);
		return root;
	}

	// Time complexity is O(n).
	// Space complexity is O(n).
}
End
捧个钱场？