Reverse Linked List

Algorithms
linked list, recursion
  • The most classic question in linked list

206. Reverse Linked List

Iteration

  • 其实就是双指针prev, cur同步移动修改链表结构
  • nxt指针暂存下一个指针的位置，最后prev到cur，cur到nxt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Iteration
# Time : O(n), Space : (1)
class Solution(object):
    def reverseList(self, head):
        prev, cur = None, head
        while cur:

            # Step1. Save the node, do not lost any control!
            nxt = cur.next

            # Step2. Modifying
            cur.next = prev

            # Step3. Iterative traverse next node
            prev = cur
            cur = nxt

        return prev

Recursion

  • 求n个node的情况，找n-1个node的情况如何拼起来
    • next->next = curr (subproblem head指向current node)
    • curr->next = null (current node’s next is set to null)
1
2
3
4
5
6
7
8
9
10
11
12
# Time : O(n), Space : (n)
class Solution(object):
    def reverseList(self, head):
        # Base Case
        if not head or not head.next:
            return head

        nhead = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return nhead

92. Reverse Linked List II

  • Reverse Linked List only from position m to position n
  • 链表的操作需要像细心的医生，一根根的线要细心搭好
    • dummyNode => get the control of the first head
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def reverseBetween(self, head, m, n):
        if m == n: return head

        # Step1. Previous node of the start position
        dummyNode = ListNode(0)
        dummyNode.next = head
        start = dummyNode
        for _ in xrange(m-1):
            start = start.next

        # Step2. Reverse from n to m
        prev, cur = start.next, start.next.next
        for _ in xrange(n-m):
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt

        # Step3. (Amazing Point of this question!)
        start.next.next = cur
        start.next = prev
        return dummyNode.next

24. Swap Nodes in Pairs

Iteration

  • 4 pointers
  • 一两个指针为一块，保留当前块的previous指针和块后next指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def swapPairs(self, head):
        if not head or not head.next:
            return head

        dummyNode = ListNode(0)
        dummyNode.next = head
        prev, p1 = dummyNode, head
        while p1 and p1.next:
            p2 = p1.next
            nxt = p2.next

            prev.next = p2
            p2.next = p1
            p1.next = nxt

            prev = p1
            p1 = nxt
        return dummyNode.next

Recursion

  • Only have to care about relation between n and n-2
1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def swapPairs(self, head):
        # Base Case
        if not head or not head.next:
            return head

        p1 = head
        p2 = head.next
        nxt = self.swapPairs(p2.next)
        p1.next = nxt
        p2.next = p1
        return p2

25. Reverse Nodes in k-Group

  • 算是Recursion的写法，Case 2 当中这个previous指针的赋值十分巧妙！正好需要翻转的链表第一个要连接的位置是后面链表的头！完美拼接！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def reverseKGroup(self, head, k):
        if not head or not head.next:
            return head

        cur = head
        cnt = 0
        while cur and cnt < k:
            cur = cur.next
            cnt += 1

        # case 1 : less than k nodes
        if cnt < k:
            return head

        # case 2 : reverse the k nodes
        prev = self.reverseKGroup(cur, k)
        cur = head
        for _ in xrange(k):
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        return prev

Convert a linked list

N1->N2->N3->N4->N5->N6->….->Nn->null (convert to) N1->Nn->N2->Nn-1->….

  • Step1. Find the middle node of the linked List
  • Step2. reverse the 2nd half
  • Step3. Merge two linked list into one long

from Google Phone Interview

  • you can not modify the structure of linked list
  • can you do it in sublinear space complexity?
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
# Time : O(n), Space : O(sqrt(n))
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

import math

class Solution(object):
    def PrintLinkedListInReverseOrder(self, head):
        if not head:
            return

        # Calculate the length
        length = 0
        cur = head
        while cur:
            cur = cur.next
            length += 1

        # Space : O(sqrt(n)
        n = int(math.sqrt(length))
        stack = []
        cur = head
        while cur:
            stack.append(cur)
            for _ in range(n):
                if cur: cur = cur.next

        while stack:
            self.helper(stack.pop(), n)


    def helper(self, node, n):
        if not node or n == 0:
            return
        self.helper(node.next, n-1)
        print(node.val)
        return


node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

sol = Solution()
sol.PrintLinkedListInReverseOrder(node1)
Share

DP - Sequence

Algorithms
dp

Input is a single sequence, we should get the properties of previous i elements

  • state : dp[i] is previous i elements position/numbers/charaters
  • function : dp[i] = dp[j]… (j < i)
  • initialize : dp[0] … (means no element in the array)
  • answer : dp[n] …

Longest/Maximum Sequence

  • Sub-array: contiguous elements in an array，number is $n^2$
  • Sub-sequence: not necessarily contiguous，number is n!

674. Longest Continuous Increasing Subsequence

  • dp[i] = dp[i-1] + 1 if nums[i] > nums[i-1] else 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Time : O(n), Space : O(n)
class Solution(object):
    def findLengthOfLCIS(self, nums):
        if not nums: return 0

        n = len(nums)
        dp = [0] * n
        dp[0] = 1

        for i in xrange(1, n):
            if nums[i] > nums[i-1]:
                dp[i] = dp[i-1] + 1
            else:
                dp[i] = 1
        return max(dp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Time : O(n), Space : O(1)
class Solution(object):
    def findLengthOfLCIS(self, nums):
        if not nums:
            return 0

        n = len(nums)
        res = 1
        cur = 1

        for i in xrange(1, n):
            if nums[i] > nums[i-1]:
                cur += 1
                res = max(res, cur)
            else:
                cur = 1
        return res

300. Longest Increasing Subsequence

dp[i] represents from the 0-the element to the i-th element, including the i-th element, the lenght of the longest ascending subsequence.

  • Base Case : dp[0] = 1
  • Induction Rule : dp[i] = max(dp[i], dp[j] + 1 if nums[i] > nums[j])
1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums:
            return 0

        n = len(nums)
        dp = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

53. Maximum Subarray

  • State : dp[i] represents [from the 0-th element to the i-the element] the maximum sum of a subarray, including the i-th element.
1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def maxSubArray(self, nums):
        if not nums:
            return 0

        n = len(nums)
        dp = [0] * n
        res = dp[0] = nums[0]
        for i in xrange(1, n):
            dp[i] = max(nums[i], nums[i] + dp[i-1])
            res = max(res, dp[i])
        return res
  1. Improve Space Complexity
  • what if we want to optimize the space complexity?
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution(object):
        def maxSubArray(self, nums):
            if not nums:
                return 0

            n = len(nums)
            res = cur = nums[0]
            for i in xrange(1, n):
                cur = max(nums[i], nums[i] + cur)
                res = max(res, cur)
            return res
  1. What if we want you to return the start and end indices of the solution array?
  • when to move the start and end?
  • need another two variables sol_start, sol_end, instead of global max length
  • State : dp[i] means ending with i

70. Climbing Stairs

1
2
3
4
5
6
7
class Solution(object):
    def climbStairs(self, n):
        dp = [0] * (n + 1)
        dp[0] = dp[1] = 1
        for i in xrange(1, n):
            dp[i+1] = dp[i] + dp[i-1]
        return dp[-1]

746. Min Cost Climbing Stairs

  • State : dp[i] means the min cost to get stair[i]
1
2
3
4
5
6
7
class Solution(object):
    def minCostClimbingStairs(self, cost):
        n = len(cost)
        dp = [0] * (n + 1)
        for i in xrange(2, n+1):
            dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
        return dp[-1]

403. Frog Jump

  • states are different! add a speed states!!!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution(object):
        def canCross(self, stones):
            n = len(stones)
            dp = [set() for _ in range(n)]
            dp[0].add(1)

            for i in range(1, n):
                for j in range(i):
                    gap = stones[i] - stones[j]
                    if gap in dp[j]:
                        dp[i].add(gap - 1)
                        dp[i].add(gap)
                        dp[i].add(gap + 1)
            return len(dp[-1]) != 0

Prefix Sum

Given Array A[1..n]，Prefix Sum Array PrefixSum[1..n] defined as：
PrefixSum[i] = A[0]+A[1]+…+A[i-1]；

e.g. A[5,6,7,8] –> PrefixSum[5,11,18,26]
PrefixSum[0] =A[0] ;
PrefixSum[1] =A[0] + A[1] ;
PrefixSum[2] =A[0] + A[1] + A[2] ;
PrefixSum[3] =A[0] + A[1] + A[2] + A[3] ;

303. Range Sum Query - Immutable

Given an immutable array, call rangeSum multiple times!

1
2
3
4
5
6
7
8
9
10
11
12
class NumArray(object):
    # Time : O(n), Space : O(n)
    def __init__(self, nums):
        self.preSum = [0]
        n = len(nums)
        s = 0
        for i in xrange(n):
            s += nums[i]
            self.preSum.append(s)
    # Time : O(1)
    def sumRange(self, i, j):
        return self.preSum[j+1] - self.preSum[i]
  • Follow up : What if the array is mutable?

304. Range Sum Query 2D - Immutable

  • We use preSum trick in the array! How about the matrix?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class NumMatrix(object):
    # Time : O(mn), Space : O(mn)
    def __init__(self, matrix):
        if not matrix:
            self.dp = []
            return
        m, n = len(matrix), len(matrix[0])
        self.dp = [[0] * (n+1) for _ in xrange(m+1)]
        dp = self.dp
        for i in xrange(1, m+1):
            for j in xrange(1, n+1):
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1]

    # Time : O(1)
    def sumRegion(self, row1, col1, row2, col2):
        if not self.dp:
            return 0
        return self.dp[row2+1][col2+1] - self.dp[row2+1][col1] - self.dp[row1][col2+1] + self.dp[row1][col1]

363. Max Sum of Rectangle No Larger Than K

  • How many sub-matrix are there in the matrix?
  • O($n^2$ * $n^2$) = O($n^4$)

解法1.Naive

计算矩阵和O($n^2$), 总Time:O($n^6$)

解法2.PreSum优化矩阵和计算

计算矩阵和O(1), 总Time:O($n^4$)
Space:O($n^2$)用来存左上角(0,0)->右下角(i,j)的矩阵和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object): # TLE
    def maxSumSubmatrix(self, matrix, k):
        if not matrix: return 0
        m, n = len(matrix), len(matrix[0])

        # PreSum matrix
        dp = [[0] * (n+1) for _ in xrange(m+1)]
        for i in xrange(1, m+1):
            for j in xrange(1, n+1):
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1]

        def sumRegion(row1, col1, row2, col2):
            return dp[row2+1][col2+1] - dp[row2+1][col1] - dp[row1][col2+1] + dp[row1][col1]

        res = -float('inf')
        for i in xrange(m):
            for j in xrange(n):
                for li in xrange(i, m):
                    for lj in xrange(j, n):
                        s = sumRegion(i, j, li, lj)
                        if s <= k:
                            res = max(res, s)
        return res

解法3.极其巧妙！

1 pre-processing 预处理 1D

从上到下做1D的preSum, O($n^2$)

2 任意取两行压缩成一个Array

瞬间把一个2D的matrix经过O($n^2$)转化成了1D的array

3 求一个Array里不大于k的连续subarray

新问题：求数组里不大于k的连续subarray O(nlogn)

TODO : python没有treeset的怎么搞？

560. Subarray Sum Equals K

  • Brute Force : $n^2$ subarray，Sum O($n$), Total O($n^3$)

Sol1. preSum

Improve Sum O($n^2$) to O(n)，but still O($n^2$), TLE

Sol2. HashTable, O(n)

A[0] + A[1] + … + A[j] = V

  • preSum[j] - preSum[i] = V similar to the Two Sum Problem，Query wether another part in preSum Array?
1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def subarraySum(self, nums, k):
        preSum = defaultdict(int)
        s = count = 0
        preSum[0] = 1
        for n in nums:
            s += n
            if (s - k) in preSum:
                count += preSum[s - k]
            sums[s] += 1
        return count

325. Maximum Size Subarray Sum Equals k

longest subarray sum equals to k

  • preSum + HashTable
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def maxSubArrayLen(self, nums, k):
        if not nums: return 0

        preSum = {}
        preSum[0] = -1
        s = res = 0
        for i, n in enumerate(nums):
            s += n
            pre = s - k
            if pre in preSum:
                res = max(res, i-preSum[pre])

            if s not in preSum:
                preSum[s] = i
        return res
Share

Tree Recursion

Algorithms
recursion, tree

Basic

  • Binary tree 往往是最常见的，和recursion结合最紧密的面试题目类型

    • 树本身就是Recursive的结构！
    • 每层的node具备的性质，传递的值和下一层的性质往往一致。比较容易定义recursive rule
    • Base case(generally):null pointer under the leaf node, Base case usually refers to the null childNode below leaf.

  • Way of thinking (相当于后序遍历 - int ,bool,etc.)

    • 1.What do you expect from your lchild/rhild?
      (usually it is the return type of the recursion type)
    • 2.What do you want to do in the current layer?
    • 3.What do you want to report to your parent?(same as Q1 == Q3)

104. Maximum Depth of Binary Tree

  • 1 Child: 问左右两个孩子要一个值
  • 2 Current: 当前层拿到左右孩子的值可以做些处理
  • 3 Parent: 向父节点返回的值和child要的值要一样就接上了！！
1
2
3
4
5
6
7
8
9
# Time : O(n), Space : O(n)
# Post Order
class Solution(object):
    def maxDepth(self, root):
        if not root:
            return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        return max(left,right) + 1

111. Minimum Depth of Binary Tree

每个节点的状态可以划分为：

  • 叶子节点 - lchild is None, rchild is None
  • 有两个孩子 - lchild is not None, rchild is not None
  • 有一个孩子 - not left child OR not right child
1
2
3
4
5
6
7
class Solution(object):
    def minDepth(self, root):
        if not root:
            return 0
        if not root.left or not root.right:
            return self.minDepth(root.left) + self.minDepth(root.right) + 1
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
  • 从下往上反值 - 统计tree里每个node的左子树有多少个node？
  • 从下往上返值 - Find the node with max difference in the total number of descendents in its left subtree and right subtree

110. Balanced Binary Tree

A binary tree in which the depth of the two subtrees of every node never differ by more than 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Time : O(nlogn), Space : O(n)
class Solution(object):
    def height(self, root):
        if not root:
            return 0
        return max(self.height(root.left), self.height(root.right)) + 1

    def isBalanced(self, root):
        if not root:
            return True
        left = self.height(root.left)
        right = self.height(root.right)
        if abs(left-right) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Time : O(n), Space : O(n)
class Solution(object):
    def isBalanced(self, root):
        return self.dfs(root) != -1

    def dfs(self, root):
        if not root:
            return 0
        left = self.dfs(root.left)
        if left == -1:  return -1

        right = self.dfs(root.right)
        if right == -1: return -1

        if abs(left - right) > 1:
            return -1
        return max(left, right) + 1

101. Symmetric Tree

  • 判断空间复杂度的时候一定要注意树不一定是balanced的！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
# Time : O(n), Space : O(n)
class Solution(object):
    def isSymmetric(self, root):
        return self.isMirror(root, root)
    def isMirror(self, root1, root2):
        if not root1 and not root2:
            return True
        elif not root1 or not root2:
            return False
        else:
            return ( root1.val == root2.val
                and self.isMirror(root1.left, root2.right)
                and self.isMirror(root1.right, root2.left))

226. Invert Binary Tree

  • 注意赋值的过程已经有改变结构，用temp来swap！
1
2
3
4
5
6
class Solution(object):
    def invertTree(self, root):
        if not root:
            return None
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

100. Same Tree

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def isSameTree(self, p, q):
        if not p and not q:
            return True
        elif not p or not q:
            return False
        else:
            return (p.val == q.val and
                   self.isSameTree(p.left, q.left) and
                   self.isSameTree(p.right, q.right))

543. Diameter of Binary Tree

  • DFS + maxDepth
  • postorder to deal with the value returned from left and right subtree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def diameterOfBinaryTree(self, root):
        if not root: return 0

        self.res = 0
        self.maxDepth(root)
        return self.res

    def maxDepth(self, root):
        if not root: return 0
        left = self.maxDepth(root.left)
        right = self.maxDepth(root.right)
        self.res = max(self.res, left + right)
        return max(left, right) + 1

222. Count Complete Tree Nodes

  • Time : O($(logn)^2$)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution:
        def countNodes(self, root):
            if not root:
                return 0
            left = self.depth(root.left)
            right = self.depth(root.right)
            if left == right:
                return (2**left) + self.countNodes(root.right)
            else:
                return (2**right) + self.countNodes(root.left)

        def depth(self, root):
            cnt = 0
            while root:
                root = root.left
                cnt += 1
            return cnt
Share

Linked List Basic

Algorithms
linked list

Introduction

Prerequisite

  • Linear Structure : Array:Phisical, Linked List:是由Pointer连起来的，不一定是物理连续的！
  • 链表的题目往往算不上“算法性”题，只是一种模拟操作的题
  • 考察的重点在于bug free，是否对写代码有熟练度！

Key Point

  • 1 When you want to de-reference a List Node, make sure it is not a NULL Pointer.
    • No matter when you use “.”, 一定要注意判断前面的Reference是否为空！！！
  • 2 Never ever lost the control of the head pointer of the Linked List.
    • 经常需要缓存nxt指针或者prev指针,都是因为当你改变链表结构的时候很容易丢失之前或者之后的信息！

Tips

  • DummyNode, Why or When should we use a dummy Node?

    • When we want to append new elements to an initially empty linkedlist, we do not have an initial head node. In this case, we can new a dummy node to act as a head node.
    • 链表的结构发生变化

  • Two or More Pointers

    • We usually use many pointer to manipulate the node of the linked list

Basic Function

Find the middle node of a linked List

  • Odd, Even
    1
    2
    3
    4
    5
    6
    7
    def findMiddleNode(head):
        if not head: return head
        fast = slow = head
        while fast.next and fast.next.next:
            fast = fast.next.next
            slow = slow.next
        return fast

Insert a node in a sorted linked list

203. Remove Linked List Elements

  • Two pointers : prev, cur
1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def removeElements(self, head, val):
        dummyNode = ListNode(0)
        dummyNode.next = head
        prev, cur = dummyNode, head
        while cur:
            if cur.val == val:
                prev.next = cur.next
            else:
                prev = cur
            cur = cur.next
        return dummyNode.next

19. Remove Nth Node From End of List

  • 快慢指针维护一个长度为n的滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def removeNthFromEnd(self, head, n):
        dummyNode = ListNode(0)
        dummyNode.next = head
        slow = fast = dummyNode
        for _ in xrange(n):
            fast = fast.next

        while fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummyNode.next

237. Delete Node in a Linked List

  • 很奇怪的一道题，做法也很奇怪
  • 往往删除单链表的一个节点，需要有头节点或者前一个节点来绕过删除的节点，这道题只给了要删除的节点(单链表拿不到previous的节点)，只能通过节点覆盖来做。
1
2
3
4
class Solution(object):
    def deleteNode(self, node):
        node.val = node.next.val
        node.next = node.next.next

83. Remove Duplicates from Sorted List

  • 和Remove Duplicate from Array一毛一样同样是同向双指针
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def deleteDuplicates(self, head):
        if not head: return head

        prev = head
        cur = head.next
        while cur:
            if cur.val == prev.val:
                prev.next = cur.next
                cur = cur.next
            else:
                prev = cur
                cur = cur.next
        return head

82. Remove Duplicates from Sorted List II

  • 删除所有的duplicate，只保留distinct的元素！
    • 1 找到重复的元素
    • 2 用while循环删除掉所有
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def deleteDuplicates(self, head):
        dummyNode = ListNode(-1)
        dummyNode.next = head
        prev = dummyNode
        cur = head
        while cur:
            if cur.next and cur.val == cur.next.val:
                while cur.next and cur.val == cur.next.val:
                    cur = cur.next
                prev.next = cur.next
            else:
                prev = cur
            cur = cur.next
        return dummyNode.next

21. Merge Two Sorted Lists

  • DummyNode的使用
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def mergeTwoLists(self, l1, l2):
        dummyNode = ListNode(-1)
        cur = dummyNode
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next
        cur.next = l1 if l1 else l2
        return dummyNode.next

23. Merge k Sorted Lists

  • heap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Time : O(nlogk), Space : (k)
class Solution(object):
    def mergeKLists(self, lists):
        heap = []
        for head in lists:
            if head:
                heapq.heappush(heap, (head.val, head))

        DummyNode = ListNode(-1)
        cur = DummyNode
        while heap:
            val, node = heapq.heappop(heap)
            if node.next:
                heapq.heappush(heap, (node.next.val, node.next))
            cur.next = node
            cur = cur.next
        return DummyNode.next

138. Copy List with Random Pointer

  • Hash Table = NewNode
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def copyRandomList(self, head):
        if not head:
            return None

        # Step1. copy New Node
        cur = head
        nodeMap = {}
        while cur:
            nodeMap[cur] = RandomListNode(cur.label)
            cur = cur.next

        # Step2. link the next and random pointer
        cur = head
        while cur:
            node = nodeMap[cur]
            node.next = nodeMap[cur.next] if cur.next else None
            node.random = nodeMap[cur.random] if cur.random else None
            cur = cur.next

        return nodeMap[head]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# Recursion
class Solution(object):
    def copyRandomList(self, head):
        def copyNode(node, cache):
            if not node:
                return None

            if node in cache:
                return cache[node]

            copy = RandomListNode(node.label)
            cache[node] = copy

            copy.next = copyNode(node.next, cache)
            copy.random = copyNode(node.random, cache)
            return copy

        return copyNode(head, {})

430. Flatten a Multilevel Doubly Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def flatten(self, head):
        if not head:
            return None
        stack = []
        cur = head
        while cur:
            if cur.child:
                if cur.next: stack.append(cur.next)
                cur.next = cur.child
                cur.child.prev = cur
                cur.child = None

            if not cur.next and stack:
                temp = stack.pop()
                cur.next = temp
                temp.prev = cur

            cur = cur.next
        return head
Share

Graph

Algorithms
graph

LeetCode 上很多问题都可以抽象成 “图” ，比如搜索类问题，树类问题，迷宫问题，矩阵路径问题，等等。Graph 是非常重要而又涵盖很广的内容，以至于有单独的”图论”研究方向。

1 图的计算机表示

  1. Node / State
  2. Edge / Action
  3. Directed vs Undirected graph
  4. Representation of the graph

Edge List

题目给的Nodes and Edges(Edge List)形式的图

  • 要么考虑用Union Find，要么考虑重新建立图的表示

Adjacency Matrix

  • Pros: Representation is easy to implement. Edge removal takes O(1) time. Queries like whether there is an edge from vertex ‘u’ to vertec ‘v’ are efficient and can be done O(1)
  • Cons: Consumes more space O(V^2)(V is the number of vertex/node) Even if the graph is sparse(contains less number of edges) == waste of space

Adjacency List

Vertices/Nodes : V, Edges : E

  • Pros: Space Complexity = O(V + E). Adding a vertex.node to the graph is easier
  • Cons: Time Complexity is O(V) to check wheter there is an edge from a node to the other.(Comprared to O(1) in adjacent matrix)

Adjacency “Hash Set”

用hashset替代list表示相邻的节点，综合了Adjacency Matrix和Adjacency List的优点！

2 Graph Search Algorithm

How to describe a BFS’s action during an interview?

  • Definition 1: expand a node s, 延展一个node
  • Definition 2: generate s’s neighbor node: reach out to its neighboring node
  • Data Structure : Maintain a FIFO queue, put all generated nodes in the queue
  • Termination condition : do a loop until the queue is empty

Discussion

  • When we deal with the tree-related problem and in the meantime we need to address the relationship on the same level
  • BFS is NOT the right algorithm to find the shortest path in the graph
  • BFS 的时间空间占用以 branching factor 为底, 到解的距离 d 为指数增长；
  • BFS 空间占用上 Queue 是不会像 DFS 一样只存一条路径的，而是从起点出发越扩越大，因此会有空间不够的风险，空间占用为 O(b^d)。

Assume Input - graph adjacency “hash set”

Undirected Graph

  • Queue, visited
1
2
3
4
5
6
7
8
9
10
11
12
# 其实和Tree的BFS traversal是一样的！
# Why visited array? 如果有环的话需要，没有环的话就是tree了，所以不需要！
def BFS1():
    visited = [0] * n
    queue = collections.deque([0])
    while queue:
        node = queue.popleft()
        print(node)
        visited[node] = 1
        for nei in graph[node]:
            if visited[nei] == 0:
                queue.append(nei)

Directed Graph

  • Only directed graph has indegree and outdegree!
1
2
3
4
5
6
7
8
9
10
# 从Indegree == 0 的node开始！
def BFS2():
    queue = collections.deque([i for i in xrange(n) if indegree[i] == 0]）
    while queue:
        node = queue.popleft()
        print(node)
        for nei in graph[course]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                queue.append(nei)

Dijkstra’s Algorithm

“呆克斯戳” Best First Search, 也是BFS

  1. Usages: Find the shortest path cost from a single node (source node) to any other nodes in that graph
  2. Data Structure: Priority Queue (Min Heap)
  3. Process
  • Initial state (start node)
  • Node expansion/ Generation rule
  • Termination condition 所有点计算完毕也是”Queue is empty”
  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 and the connectivity of the 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 (非负权重)

743. Network Delay Time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
  def networkDelayTime(self, times, N, K):
      graph = [[] for _ in xrange(N+1)]
      for u, v, w in times:
          graph[u].append((v, w))

      dis = [0] + [-1] * N  
      pq = [(0, K)]

      while pq:
          w, s = heapq.heappop(pq)
          if dis[s] >= 0:
              continue
          dis[s] = w
          for nxt, nw in graph[s]:
              heapq.heappush(pq, (w+nw, nxt))
      return -1 if -1 in dis else max(dis)

378. Kth Smallest Element in a Sorted Matrix

  • Time : O(klogk), Space : O(k)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def kthSmallest(self, matrix, k):
        n = len(matrix)
        visited = set([(0, 0)])
        heap = [(matrix[0][0], 0, 0)]

        for _ in xrange(k):
            val, x, y = heapq.heappop(heap)

            # next row
            if x+1 <= n-1 and (x+1, y) not in visited:
                heapq.heappush(heap, (matrix[x+1][y], x+1, y))
                visited.add((x+1,y))

            # next col
            if y+1 <= n-1 and (x, y+1) not in visited:
                heapq.heappush(heap, (matrix[x][y+1], x, y+1))
                visited.add((x,y+1))

        return val

Backtracking is just a behavior of DFS

  • DFS 的时间占用以 branching factor 为底，树的深度 m 为指数增长
  • DFS 的空间占用上，却只是 O(bm)，可视化探索过程中只把每个 Node 的所有子节点存在 Stack 上， 探索完了再 pop 出来接着探，因此储存的节点数为 O(bm)。

可以看到无论是 BFS 还是 DFS，树的 branching factor 都是对空间与时间复杂度影响最大的参数；除此之外，BFS 中最重要的是到解的距离，而 DFS 看从当前节点的深度。普遍来讲，DFS 空间上会经济一些，当然也要分情况讨论。

Undirected Graph

1
2
3
4
5
def dfs(node):
    visited.add(node)
    for nei in node.neighbors:
        if nei not in visited:
            dfs(nei)

Directed Graph

  • visited 需要 三种状态!!! 0-未访问，1-正在访问，2-已经访问

3 Application

785. Is Graph Bipartite?

  • BFS的做法有一个问题，就是这个图可能不是连通图！！！所以要遍历所有点！
  • 所有点有两次一次push进Queue，一次pop出Queue！
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
class Solution(object):
    def isBipartite(self, graph):
        n = len(graph)
        visited = [False] * n
        A, B = set(), set()
        for i in range(n):
            if visited[i]:
                continue

            queue = collections.deque([(i,0)])
            while queue:
                node, level = queue.popleft()

                if level:
                    B.add(node)
                else:
                    A.add(node)

                if visited[node]:
                    continue

                for nei in graph[node]:
                    queue.append((nei, 1 - level))
                visited[node] = True
        return not A&B

133. Clone Graph

克隆Graph，很多graph都是用HashTable一一映射

  • Hash Table 新旧node一一映射，再把关系同样映射！
  • DFS，BFS都可以把所有node遍历一遍就好
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
# BFS
class Solution:
    def cloneGraph(self, node):
        if not node:
            return None

        gmap = {node:UndirectedGraphNode(node.label)}
        queue = collections.deque([node])
        while queue:
            nnode = queue.popleft()
            for nei in nnode.neighbors:
                if nei not in gmap:
                    gmap[nei] = UndirectedGraphNode(nei.label)
                    queue.append(nei)
                gmap[nnode].neighbors.append(gmap[nei])
        return gmap[node]

# DFS
class Solution:
    def cloneGraph(self, node):
        return self.dfs(node, {})

    def dfs(self, node, cache):
        if not node:
            return None

        if node in cache:
            return cache[node]

        copy = UndirectedGraphNode(node.label)
        cache[node] = copy

        for nei in node.neighbors:
            nnei = self.dfs(nei, cache)
            copy.neighbors.append(nnei)
        return copy
Share

Union Find 并查集

Algorithms
graph

What is Union Find ?

  • Union-Find算法(并查集算法)是解决动态连通性（Dynamic Conectivity）问题的一种算法，”人以类聚,物以群分”
  • 一种用来解决集合查询合并的数据结构，支持 O(1)find, O(1)union
  1. 查询 Find
    • 确定某个元素x属于哪一个集合
  2. 合并 Union
    • 将两个集合合并

应用场景

  1. Computer Network
    • 两个网络节点是否联通
    • 最小的布线使得整个网络联通
  2. Social Network
    • Linkedin 两个用户可能认识的人
  3. 集合论

Union Find vs DFS

在对问题进行建模的时候，我们应该尽量想清楚需要解决的问题是什么!
因为模型中选择的数据结构和算法显然会根据问题的不同而不同!

  • Union Find - 给出两个节点，判断它们是否连通，如果连通，不需要给出具体的路径
  • DFS - 给出两个节点，判断它们是否连通，如果连通，需要给出具体的路径

Algorithm

Quick-Find

有点类似于染色的过程，每个节点一个颜色，然后相同的节点设置成相同的颜色。
quick-find算法十分直观符合简单的思考过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
# Time : O(1)
def find(x):
    return root[x]

# Time : O(n)
def union(x, y):
    rootx = root[x]
    rooty = root[y]
    if rootx == rooty:
        return
    for i in xrange(len(root)):
        if root[i] == rootx:
            root[i] = rooty

每次添加新路径(Union)就是 “牵一发而动全身”，想要解决这个问题，关键就是要提高union方法的效率，让它不再需要遍历整个数组。

Quick-Union

  • 以树的思想，表示集合！！！
  • 这是UF算法里最关键的思路，以树的形式表示集合，这样组织正好可是很高效的实现find和union!
1
2
3
4
5
6
7
8
9
10
11
12
# Time : O(Tree Height), Worst Case O(n)
# Recursion
def find(x):
    if root[x] == x:
        return x
    return find(root[x])

# Iteration
def find(x):
    while root[x] != x:
        x = root[x]
    return x
1
2
3
4
5
6
# Time : O(Tree Height), Worst Case O(n)
def union(x, y):
    rootx = find(x)
    rooty = find(y)
    if rootx != rooty: 判断两个Element在不在同一个集合当中
        root[rootx] = rooty

Weighted Quick-Union

既然树的高度成为制约时间复杂度的瓶颈，我们就想办法让树平衡！

  • 以Quick union为基础，我们 额外利用一个size[]保存每一个联通集中对象的数量。
  • 在调用union()的时候，我们总是把 对象数目较少的联通集连接到对象数目较多的联通集 中。
  • 通过这种方式，我们可以在一定程度上缓解树的高度太大的问题，从而改善Quick union的时间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Time : O(logn)
def find(x):
    if root[x] == x:
        return x
    return find(root[x])

# Time : O(logn)
def union(x, y):
    rootx = find(x)
    rooty = find(y)
    if size[rootx] >= size[rooty]:
        root[rooty] = rootx
        size[rootx] += size[rooty]
    else:
        root[rootx] = rooty
        size[rooty] += size[rootx]

Path Compression

随着数据的增加，树的深度不断增加，性能会逐渐变差。这个时候，如果我们在计算一个node的root时，将node为根的树摘下来，挂在当前树的根结点上，会降低树的深度，也就是提高效率，降低时间复杂度。

1
2
3
4
5
6
7
8
9
# Path Compression 是在find的过程当中处理的
def find(x):
    if root[x] == x:
        return x

    # make every other node in path point to its grandparent.
    root[x] = find(root[x]) # Only one extra line

    return root[x]

Weighted Quick-Union With Path Compression

Proof is very difficult, But the algorithm is still simple!

1
2
3
4
5
6
7
8
9
10
11
12
13
# Weighted 是体现在Union的过程当中
# Time : Very Near to O(1)
def union(x, y):
    rootx = find(x)
    rooty = find(y)
    if rootx == rooty:
        return
    if size[rootx] >= size[rooty]:
        root[rooty] = rootx
        size[rootx] += size[rooty]
    else:
        root[rootx] = rooty
        size[rooty] += size[rootx]

Connected

查询两个元素是否在同一个集合内。

LintCode 589. Connecting Graph

Given n nodes in a graph labeled from 1 to n. There is no edges in the graph at beginning.

You need to support the following method:

  1. connect(a, b), add an edge to connect node a and node b.
  2. query(a, b), check if two nodes are connected
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class ConnectingGraph:
    def __init__(self, n):
        self.root = range(n+1)

    # Find the Root of node x
    def find(self, x):
        root = self.root # tip1 : root在类里面要加上"self."
        if root[x] == x:
            return x
        root[x] = self.find(root[x])
        return root[x]

    def union(self, x, y):
        root = self.root
        rootx = self.find(x) # tip2 : root[x] vs find(x)
        rooty = self.find(y)
        if rootx != rooty:
            root[rootx] = rooty

    def connect(self, a, b):
        self.union(a, b)

    def query(self, a, b):
        return self.find(a) == self.find(b)

LintCode 590. Connecting Graph II

  • 统计每个联通块的元素个数
  • query(a), Returns the number of connected component nodes which include node a.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class ConnectingGraph2:
    def __init__(self, n):
        self.root = range(n+1)
        self.size = [1] * (n+1)

    def find(self, x):
        root = self.root
        if root[x] == x:
            return x
        root[x] = self.find(root[x])
        return root[x]

    def connect(self, a, b):
        root = self.root
        size = self.size
        roota = self.find(a)
        rootb = self.find(b)
        if roota != rootb:
            root[roota] = rootb
            size[rootb] += size[roota]

    def query(self, a):
        return self.size[self.find(a)]

130. Surrounded Regions

  • 解法1 DFS

从边缘的’O’出发，通过DFS，所有能够遍历的’O’都可以暂时被标记为’#’，那么剩下未能被标记的’O’说明被surrounded，需要在遍历结束之后全部转为’X’

  • 解法2 Union Find

将与边缘相连通的’O’全部union到一个dummy node（也可以用hasEdge[]来存储，不过内存占用更多,
最终将没有和这个dummy node是一个component的’O’点全部标记为’X

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
class UnionFind(object):
    def __init__(self, n):
        self.root = range(n)

    def find(self, x):
        root = self.root
        if root[x] == x:
            return x
        root[x] = self.find(root[x])
        return root[x]

    def union(self, x, y):
        root = self.root
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx != rooty:
            # tip : 为了总是以dummy node(total)为父节点
            root[min(rootx, rooty)] = max(rootx, rooty)

class Solution(object):
    def solve(self, board):
        if not board:
            return
        m, n = len(board), len(board[0])
        total = m*n
        uf = UnionFind(total+1)
        grid = board
        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j] == 'X':
                    continue
                # Connect to "total" root
                if i == 0 or j == 0 or i == m-1 or j == n-1:
                    uf.union(total, i*n+j)
                else:
                    d = [(1, 0), (0, 1), (-1, 0), (0, -1)]
                    for k in xrange(4):
                        ni, nj = i + d[k][0], j + d[k][1]
                        if grid[ni][nj] == 'O':
                            uf.union(ni*n + nj, i*n + j)
        for i in xrange(m):
            for j in xrange(n):
                if grid[i][j] == 'X':
                    continue
                if uf.find(i*n + j) != total:
                    grid[i][j] = 'X'

737. Sentence Similarity II

典型的Union Find 应用题，两个单词是不是similarity其实就是两个单词在不在同一个集合内(connected 操作)！

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
class UnionFind(object):
    def __init__(self, n):
        self.root = range(n)

    def find(self, x):
        root = self.root
        if root[x] == x:
            return x
        root[x] = self.find(root[x])
        return root[x]

    def union(self, x, y):
        self.root[self.find(x)] = self.find(y)

class Solution(object):
    def areSentencesSimilarTwo(self, words1, words2, pairs):
        m, n = len(words1), len(words2)
        if m != n: return False

        # 建立words到index的映射关系！UnionFind 只支持数字的index！
        uf = UnionFind(len(pairs)*2)
        cnt = 0
        pdic = {}
        for w1, w2 in pairs:
            if w1 not in pdic:
                pdic[w1] = cnt
                cnt += 1
            if w2 not in pdic:
                pdic[w2] = cnt
                cnt += 1
            uf.union(pdic[w1], pdic[w2])

        for w1, w2 in zip(words1, words2):
            if w1 == w2:
                continue
            if w1 not in pdic or w2 not in pdic:
                return False
            if uf.find(pdic[w1]) != uf.find(pdic[w2]):
                return False
        return True

统计连通块的个数

the number of connected components.

LintCode 591. Connecting Graph III

  • Query() - Returns the number of connected component in the graph
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class ConnectingGraph3:
    def __init__(self, n):
        self.root = range(n+1)
        self.cnt = n

    def find(self, x):
        root = self.root
        if root[x] == x:
            return x
        root[x] = self.find(root[x])
        return root[x]

    def connect(self, a, b):
        root = self.root
        roota = self.find(a)
        rootb = self.find(b)
        if roota != rootb:
            root[roota] = rootb
            self.cnt -= 1

    def query(self):
        return self.cnt

323. Number of Connected Components in an Undirected Graph

  • 解法1. DFS

将Graph原本的nodes和edges表达形式，改成hash做的邻接表，这个就可以查询从每个节点出发到的节点！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def countComponents(self, n, edges):
        visited = [0] * n
        graph = [set() for _ in xrange(n)] # Adjacent Table
        for i, j in edges:
            graph[i].add(j)
            graph[j].add(i)
        res = 0
        for i in xrange(n):
            if visited[i] == 1:
                continue
            self.dfs(i, visited, graph)
            res += 1
        return res


    def dfs(self, n, visited, graph):
        if visited[n] == 1:
            return
        visited[n] = 1
        for i in graph[n]:
            self.dfs(i, visited, graph)

  • 解法2. Union Find
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def countComponents(self, n, edges):
        root = range(n)
        self.cnt = n
        def find(x):
            if root[x] == x:
                return x
            root[x] = find(root[x])
            return root[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                root[rootx] = rooty
                self.cnt -= 1

        for i, j in edges:
            union(i, j)
        return self.cnt

305. Number of Islands II

实时放入island显示出联通块的个数，算是一个online的算法！

  • 原始UF算法是一维的，2D坐标和1D坐标的转化
  • 体现Union Find的Online特性，可以实时添加边！
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
# Time : O(m * n + k)
class UnionFind(object):
    def __init__(self, n):
        self.root = [-1] * n
        self.cnt = 0

    def find(self, x):
        root = self.root
        if root[x] == x:
            return x
        root[x] = self.find(root[x])
        return root[x]

    def add(self, x):
        self.root[x] = x
        self.cnt += 1

    def union(self, x, y):
        root = self.root
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx != rooty:
            root[rootx] = rooty
            self.cnt -= 1

class Solution(object):
    def numIslands2(self, m, n, positions):
        uf = UnionFind(m * n)
        res = []
        d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        for i, j in positions:
            p = i*n + j
            uf.add(p)
            for k in range(4):
                ni, nj = i + d[k][0], j + d[k][1]
                q = ni * n + nj
                if ( 0 <= ni <= m-1 and
                     0 <= nj <= n-1 and
                     uf.root[q] != -1):
                    uf.union(p, q)
            res.append(uf.cnt)
        return res

547. Friend Circles

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def findCircleNum(self, M):
        n = len(M)
        root = range(n)
        self.cnt = n

        def find(x):
            if root[x] == x:
                return x
            root[x] = find(root[x])
            return root[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                root[rootx] = rooty
                self.cnt -= 1

        for i in xrange(n):
            for j in xrange(i+1, n):
                if M[i][j]:
                    union(i, j)
        return self.cnt

Redundant Connection

261. Graph Valid Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def validTree(self, n, edges):
        root = range(n)
        self.cnt = n
        def find(x):
            if root[x] == x:
                return x
            root[x] = find(root[x])
            return root[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                root[rootx] = rooty
                self.cnt -= 1
                return True
            return False

        for i, j in edges:
            if not union(i, j):
                return False
        return self.cnt == 1

684. Redundant Connection

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def findRedundantConnection(self, edges):
        root = range(1001)

        def find(x):
            if root[x] == x:
                return x
            root[x] = find(root[x])
            return root[x]

        for i, j in edges:
            rooti = find(i)
            rootj = find(j)
            if rooti == rootj:
                return [i, j]
            root[rooti] = rootj

685. Redundant Connection II

  • Case1: There is a loop in the graph, and no vertex has more than 1 parent.
    • 有环，且没有入度大于1的node => Union Find
  • Case2: A vertex has more than 1 parent, but there isn’t a loop in the graph.
    • 无环，且有入度大于2的node => last node (indegree > 1)
  • Case3: A vertex has more than 1 parent, and is part of a loop.
    • 有环，且有入度大于2的node
    • 这种复杂的情况怎么筛选?
    • Delete the second edge!
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
class Solution(object):
    def findRedundantDirectedConnection(self, edges):
        n = len(edges)
        parent = [0] * (n+1)
        ans = None
        # Step1 : calculate indegree > 1 node
        for i in xrange(n):
            u, v  = edges[i]
            if parent[v] == 0:
                parent[v] = u
            else:
                ans = [[parent[v], v], [u, v]]
                # !!! Delete the second Edge
                edges[i][1] = 0

        # Step2 : Union Find detect cycle
        root = range(n+1)
        def find(x):
            if root[x] == x:
                return x
            return find(root[x])

        for u, v in edges:
            rootu = find(u)
            rootv = find(v)
            if rootu == rootv: # Detect Cycle
                if not ans:
                    return [u, v]
                else:
                    return ans[0]
            root[rootu] = rootv
        return ans[1]
Share

OOD in Interview

OOD

总结自:九章算法 - OOD1

OOD in Interview

Everything is an object, Usable!!!

  • 面试频率
    • Phone interview 低
    • Onsite interview 中高频
  • 高频公司
    • Amazon, Bloomberg, TripAdvisor, EMC, Uber…
  • 主要考察CS设计的基本素养，属于开放型设计类题目，能用上OOD的常见的一些设计思想！

OOA(Analysis) -> OOD(Design) -> OOP(Programming)

  • OOD问法
    • Can you design a … system? little amount of coding
    • Can you … for … system? need implementation

OOD要避免的情况

  • 1 不问清需求就开始设计，一定要和面试官!沟通”甲方”的需求！
    • Communication
  • 2 没有理解面试官想要问System Design，还是OOD，还是算法！
    • Think loud
  • 3 思路混乱，反复更改之前的设计！Usable！！！就好
    • Correctness & Reasonable
  • use case

“SOLOD”原则

  • S - Single responsibility principle
    • 一个类应该有且只有一个去改变它的理由，这意味着一个类应该只有一项工作。
  • O – Open close principle
    • 对象或实体应该对扩展开放，对修改封闭 (Open to extension, close to modification)
  • L - Liskov substitution principle 里氏替换原则
    • 任何一个子类或派生类应该可以替换它们的基类或父类
  • I - Interface segregation principle 接口分离原则
    • 不应该强迫一个类实现它用不上的接口 Implement
  • D - Dependency inversion principle 依赖反转原则
    • 抽象不应该依赖于具体实现，具体实现应该依赖于抽象
    • 只能class 依赖于Abstract, Imterface

Design an elevator system

Clarify : 通过和面试官交流，去除题目中的歧义，确定答题范围

What? - 什么?

  • 针对题目中的关键字来􏰁问，帮助自己更好的确定答题范围
  • 大多数的关键字为名词，通过名词的属性来考虑
  • Elevator, Building

How? - 怎样?

  • 针对问题主题的规则来􏰁问，帮助自己明确解题方向。
  • 此类问题没有标准答案，你可以􏰁出一些解决方法，通过面试官的反应， 选择一个你比较有信心(简单)的方案
  • Rule
    • 同向 > 静止 > 反向，当运行时不能按下反向的楼层
    • 电梯至少需要三种状态，并且要知道当前在哪一层

Who? - 谁?

  • 设计由人主导 VS. 设计由系统主导?
  • (Optional)通过思考题目当中是否有人的出现，来帮助确定解题范围
  • 一般可以考虑人的角色以及人的属性，看是否题目需要

When? - 什么时间?

  • (Optional)通过思考题目当中和时间相关的属性，来帮助确定解题范围
  • 和时间相关的问题一般都比较细节，可能会有意想不到的帮助

Think Process

Core Object

为了完成设计，需要哪些class？

  • 以一个Object为基础，往往就是需要设计的system！
  • 确定objects之间的映射关系(4~5个Object)

Access modifier

  • package
    • 如果什么都不声明，变量和函数都是package level visible的，在同一个package内的其他类都可以访问
  • public
    • 如果声明为public，变量和函数都是public level visible的，任何其他的类都可以访问
    • 用”+”表示一个变量或者函数为public
  • private
    • 如果声明为private，变量和函数都是class level visible的，这是所有access modifier中限制最多的一个。
    • 仅有定义这些变量和函数的类自己可以访问。
    • 在类图中，用”-”表示一个变量或者函数为private
  • protected
    • 如果声明为protected，变量和函数在能被定义他们的类访问的基础上，还能够被该类的子类所访问。
    • protected也是OOD当中实现继承的重要手段
    • 在类图中，用”#”表示一个变量或者函数为protected

Use Cases

e.g. Elevator

  • Take external request
  • Take internal request
  • Open gate
  • Close gate
  • Check weight

Class diagram 类图

  • 为什么要画类图?
    • 可交付，MinimalViableProduct
    • 节省时间，不容易在Coding上挣扎
    • 建立在Usecase上，和之前的步骤层层递进，条例清晰，便于交流和修改
    • 如果时间允许/面试官要求，便于转化成Code
  • 怎么画类图?
    • 遍历你所列出的usecases
    • 对于每一个usecase，更加详细的􏰀述这个usecase在做什么事情 (例如:take external request -> ElevatorSystem takes an external request, and decide to push this request to an appropriate elevator)
    • 针对这个􏰀述，在已有的Coreobjects里填充进所需要的信息

Challenge

  • What if I want to apply different ways to handle external requests during different time of a day?
    • Solution 1: if - else
    • Solution 2: Strategy design pattern
Share

Binary Indexed Tree

Algorithms
tree

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

What is Binary Indexed Tree？

1
2
3
4
5
# PrefixSum
def update(idx, n):
# O(n), update idx-th num in the array
def rangeSum(idx1, idx2):
# O(1), calculate the sum from idx1-th to idx2-th in the arrayk

传统的数组单点修改的复杂度为 O(1)，查询子段和的复杂度为 O(n)
前缀和数组单点修改的复杂度为 O(n)，查询子段和的复杂度为 O(1)

  • Binary Indexed Tree 修改和查询子段和复杂度均为 O(logn)
  • 所以在多组查询或动态查询时，用树状数组可以有效减小耗时，提高程序效率。

Binary Indexed Tree vs Segmented Tree

  • 树状数组 容易实现，代码量小，时间复杂度低，并且经过数学处理后也可以实现成段更新。线段树也可以做到和树状数组一样的效果，但是代码要复杂得多。
  • 不过要注意，一般情况下 树状数组能解决的问题线段树都能解决，反之有些线段树能解决的问题树状数组却不行。

Operation

1 Build

从已知数组构建树状数组就是把线性的数组变成一棵树。那么，树状数组是如何把线性结构的数组变成一棵树的呢？以下以一个长度为8的数组为例：

原始数组：

1
A[1], A[2], A[3], A[4], A[5], A[6], A[7], A[8]

在修改和查询子段和时，很容易想到一种类似二分的想法来构建一棵树状的数组来保存原数组的所有信息。

1
2
3
4
5
6
7
8
C1 = A1
C2 = C1 + A2 = A1 + A2
C3 = A3
C4 = C2 + C3 + A4 = A1 + A2 + A3 + A4
C5 = A5
C6 = C5 + A6 = A5 + A6
C7 = A7
C8 = C4 + C6 + C7 + A8 = A1 + A2 + A3 + A4 + A5 + A6 + A7 + A8

从中可以发现，若结点的标号为 n ，则该结点的求和区域长度为 2k ，此处的 k 为 n 的二进制表示的末尾 0 的个数。

1
2
# 只保留n的二进制里最低位的1
2^k = n & (n ^ (n-1)) = n & (-n)

  • 前n项和分别保存在n二进制表示的每个“1”表示
i 二进制 包含A的个数
1 0001 1
2 0010 2
3 0011 3
4 0100 4
5 0101 1
6 0110 2
7 0111 1
8 1000 8 
1
2
3
4
5
6
7
8
9
10
# Time : O(nlogn)
def build(self, nums):
    n = len(nums)
    # BIT 数组比原数组多一位！
    A, C = nums, [0] * (n + 1)
    for i in range(n):
        k = i + 1 # Start From i+1
        while k <= n:
            C[k] += A[i]
            k += (k & -k) # Next Parent Node

2 Update

  • C[i]的父节点为C[i + i & (-i)]

当我们修改A[i]的值时，记录变化，可以 从C[i]往根节点一路上溯，调整这条路上的所有C[p]即可，这个操作的复杂度在最坏情况下就是树的高度即O(logn)。

1
2
3
4
5
6
def update(self, i, val):
    diff, self.A[i] = val - self.A[i], val
    i += 1 # Start From i+1
    while i <= self.n:
        self.C[i] += diff
        i += (i & -i) # Next Parent Node

3 Range Sum

  • 而对于求数列的前n项和S[n]，只需找到C[n]以前（包括C[n]）的所有最大子树，把其根节点的C[c]加起来即可。
1
2
3
4
5
6
7
8
9
def sumRange(self, i, j):
    res, j = 0, j + 1
    while j: # 前j项和(j=j+1了,数组是从0开始index的！)
        res += self.C[j]
        j -= (j & -j) # Next Sum Node
    while i: # 前i-1项和
        res -= self.C[i]
        i -= (i & -i)
    return res

Application

307. Range Sum Query - Mutable

  • update & range sum

    Solution1. Update O(1), RangeSum O(n)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    class NumArray(object):

        def __init__(self, nums):
            self.nums = nums

        def update(self, i, val):
            self.nums[i] = val

        def sumRange(self, i, j):
            s = 0
            for k in range(i, j+1):
                s += self.nums[k]
            return s

Solution2. Update O(n), RangeSum O(1)

  • Prefix Sum array

Solution3. Update O(logn), RangeSum O(logn)

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
class NumArray(object):

    def __init__(self, nums):
        self.n = n = len(nums)
        self.A, self.C = nums, [0] *(n + 1)
        for i in xrange(n):
            k = i + 1 # tip1 : BIT index from 1
            while k <= n:
                self.C[k] += nums[i]
                k += k & (-k)

    def update(self, i, val):
        diff = val - self.A[i]
        self.A[i] = val # tip2 : remember to update original array
        i += 1
        while i <= self.n:
            self.C[i] += diff
            i += i & (-i)


    def sumRange(self, i, j):
        res = 0
        j += 1
        while j:
            res += self.C[j]
            j -= j & (-j)
        while i: # tip3 : excluding i, so i do not need to +1
            res -= self.C[i]
            i -= i & (-i)
        return res

308. Range Sum Query 2D - Mutable

Solution1. PrefixSum

  • Build : O(mn)
  • Update : O(n)
  • Region Sum : O(m)
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
class NumMatrix(object):

    def __init__(self, matrix):
        if not matrix:
            return

        self.matrix = matrix
        self.preSum = copy.deepcopy(matrix)

        for row in self.preSum:
            for j in range(1, len(matrix[0])):
                row[j] += row[j-1]

    def update(self, row, col, val):
        diff = val - self.matrix[row][col]
        self.matrix[row][col] = val

        for j in range(col, len(self.matrix[0])):
            self.preSum[row][j] += diff

    def sumRegion(self, row1, col1, row2, col2):
        s = 0
        for i in range(row1, row2+1):
            row_sum = self.preSum[i][col2] - (self.preSum[i][col1-1] if col1 > 0 else 0)
            s += row_sum
        return s

Solution2. BIT

  • Build : O(mn(logm)(logn))
  • Update : O(logm logn)
  • Region Sum : O(logm logn)
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
class NumMatrix(object):

    def __init__(self, matrix):
        if not matrix:
            return

        m, n = len(matrix), len(matrix[0])
        self.m, self.n = m, n
        self.matrix = matrix
        self.bit = [[0] * (n+1) for _ in xrange(m+1)]
        for i in xrange(m):
            for j in xrange(n):
                self.build(i, j)

    def build(self, row, col):
        val = self.matrix[row][col]
        i = row+1
        while i <= self.m:
            j = col + 1
            while j <= self.n:
                self.bit[i][j] += val
                j += j & (-j)
            i += i & (-i)

    def update(self, row, col, val):
        diff = val - self.matrix[row][col]
        self.matrix[row][col] = val
        i = row+1
        while i <= self.m:
            j = col + 1
            while j <= self.n:
                self.bit[i][j] += diff
                j += j & (-j)
            i += i & (-i)

    def getSum(self, row, col):
        i = row+1
        res = 0
        while i:
            j = col + 1
            while j:
                res += self.bit[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return res

    def sumRegion(self, row1, col1, row2, col2):
        return self.getSum(row2, col2) - self.getSum(row1-1, col2) - self.getSum(row2, col1-1) + self.getSum(row1-1, col1-1)

315. Count of Smaller Numbers After Self

Binary Indexed Tree & Fenwick Tree

  • 对原数组nums进行 离散化处理 排序+去重，将nums从实数范围映射到 [1, len(set(nums))]，记得到的新数组为iNums
1
2
3
4
5
6
idxes = {}
for k, v in enumerate(sorted(set(nums))):
    idxes[v] = k + 1
iNums = [idxes[x] for x in nums]
# iNums 相当于重新映射后的Array，其间数值的相对大小没有改变，
# 但是值总的范围映射到了[0, n]这样就可以作为BIT的index了！！
  • 从右向左遍历iNums，对树状数组的iNums[i]位置执行+1操作，然后统计(0, iNums[i])的区间和,也可以用线段树
  • 把计数问题转化成了求区间和的问题！
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
class FenwickTree(object):

    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (n+1)

    def add(self, i, val):
        while i <= self.n:
            self.BIT[i] += val
            i += i & -i

    def sum(self, i):
        res = 0
        while i:
            res += self.BIT[i]
            i -= i & -i
        return res

class Solution(object):
    def countSmaller(self, nums):
        if not nums: return []
        idxs = {}
        for k, v in enumerate(sorted(set(nums))):
            idxs[v] = k + 1
        n = len(nums)
        ftree = FenwickTree(n)
        res = []
        for i in xrange(n-1, -1, -1):
            res.append(ftree.sum(idxs[nums[i]]-1))
            ftree.add(idxs[nums[i]], 1)
        return res[::-1]
Share

Tree Traversal BFS

Algorithms
bfs, tree

BFS Level Order Traversal

  • When should we change layer to the next?
  1. use a new Queue to record next level!
  2. use a value to record the size of the queue on the current level

102. Binary Tree Level Order Traversal

  • use two Queue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def levelOrder(self, root):
        if not root: return []

        queue = [root]
        res = []
        while queue:
            res.append([node.val for node in queue])
            nqueue = []
            for node in queue:
                if node.left:
                    nqueue.append(node.left)
                if node.right:
                    nqueue.append(node.right)
            queue = nqueue
        return res

107. Binary Tree Level Order Traversal II

  • just reverse the results of 102?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def levelOrderBottom(self, root):
        if not root:
            return []
        queue = [root]
        res = []
        while queue:
            res.append([node.val for node in queue])
            nqueue = []
            for node in queue:
                if node.left:
                    nqueue.append(node.left)
                if node.right:
                    nqueue.append(node.right)
            queue = nqueue
        return res[::-1]

637. Average of Levels in Binary Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def averageOfLevels(self, root):
        if not root:
            return []
        res = []
        queue = [root]
        while queue:
            level = [node.val for node in queue]
            ret = 1.0 * sum(level) / len(level)
            res.append(ret)
            nqueue = []
            for node in queue:
                if node.left:
                    nqueue.append(node.left)
                if node.right:
                    nqueue.append(node.right)
            queue = nqueue
        return res

103. Binary Tree Zigzag Level Order Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def zigzagLevelOrder(self, root):
        if not root:
            return []

        queue = [root]
        res = []
        while queue:
            level = [node.val for node in queue]
            if len(res) % 2:
                level.reverse()
            res.append(level)
            nqueue = []
            for node in queue:
                if node.left: nqueue.append(node.left)
                if node.right: nqueue.append(node.right)
            queue = nqueue
        return res
  • Another Solution : Use Deque!
    In the even level:expand a node from the right end of the dequ, generate right and then left child, and insert them to the left end of the deque.

662. Maximum Width of Binary Tree

if use index to calculate whicn index in its level

  • 2 idx, 2 idx + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def widthOfBinaryTree(self, root):
        if not root:
            return 0

        queue = [(root, 0)]
        res = 1
        while queue:
            nqueue = []
            for node, idx in queue:
                if node.left:
                    nqueue.append((node.left, 2*idx))
                if node.right:
                    nqueue.append((node.right, 2*idx+1))
            if nqueue:
                res = max(res, nqueue[-1][1] - nqueue[0][1] + 1)
            queue = nqueue
        return res

Linked List Queue

  • O(1) Space complexity

116. Populating Next Right Pointers in Each Node

  • Actually its the “linked list” version BFS, so space complexity is constant!!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution:
        def connect(self, root):
            if not root:
                return

            cur = root
            while cur.left:
                head = cur.left
                while cur:
                    cur.left.next = cur.right
                    if cur.next:
                        cur.right.next = cur.next.left
                    cur = cur.next
                cur = head

117. Populating Next Right Pointers in Each Node II

  • Do not know the head of next level, so DummyNode make it easier to implement!!!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution:
        def connect(self, root):
            if not root:
                return
            
            DummyNode = TreeLinkNode(-1)
            head = root
            while head:
                DummyNode.next = None
                prev = DummyNode
                cur = head
                while cur:
                    if cur.left:
                        prev.next = cur.left
                        prev = cur.left
                    if cur.right:
                        prev.next = cur.right
                        prev = cur.right
                    cur = cur.next
                head = DummyNode.next
Share

Tree Traversal DFS

Algorithms
tree

Tree DFS

  • Recursion vs Iteration.
    Too easy to use recursion to solve the traversal problem, Why we need the iterative solution?

Java meomory area

  • STACK: storing the local variables and other information for each of the method calls
  • HEAP: allocationg spaces for dynamically created objects
  • Threads have their own stack, but they share same heap!

Python内存中没有真正的堆栈，因为所有的对象都是在堆上分配的，but python默认的递归深度是很有限的（默认是1000）

  • STACK
    • In Java, STACK is usually a size limited memory area.By default, a several thousands levels recursion call would easily eat up all the space and throw StackOverFlowException - this is something you have to keep in mind
    • Iterative way is good because it needs much less space of STACK(There is probably only O(1) method call levels, so O(1) space on STACK.)
    • It is not easy to convert all recursion solutions to a “while loop” solution without any other auxiliary data structures’ help.
1
2
3
4
5
6
7
8
# Recursive Inorder Traversal
class Solution(object):
    def inorderTraversal(self, root):
        if not root:
            return []
        self.inorderTraversal(root.left)
        print(root.val)
        self.inorderTraversal(root.right)

  • There are two paths of recursion need to follow instead of one, and we need to finish the first branch, then the second one.

  • In this case, we will need something else to help us:

    • The recursion is internally done by using STACK to maintain the method call levels and directions, we can simulate this ourselves, so a stack will be needed.
    • The difference is, we use our own stack and the space used by our own stack is on HEAP. The space consumed on STACK is trivial.
    • We do not change the total space consumption, but we move out the space consumption of STACK to HEAP!!!

144. Binary Tree Preorder Traversal

Recursion

1
2
3
4
5
6
class Solution(object):
    def preorderTraversal(self, root):
        if not root: return []
        return ([root.val]
                + self.preorderTraversal(root.left)
                + self.preorderTraversal(root.right))

Iteration (Stack)

  • 1 stack一出栈 一看见就访问！
  • 2 出栈元素的右子节点先加入栈，再加左子节点
  • 每个node其实处理了两次，一次是入栈，一次是出栈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def preorderTraversal(self, root):
        if not root:
            return []
        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            res.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
        return res

94. Binary Tree Inorder Traversal

Recursion

1
2
3
4
5
6
7
class Solution(object):
    def inorderTraversal(self, root):
        if not root:
            return []
        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)
        return left + [root.val] + right

Iteration (Stack + cur)

The problem is, we can not throw away the root in the stack before we traversed all the nodes in left subtreee. How can we know we have already traversed all the nodes in left sub?

  • The root is the top element in the stack, use a helper node to store the next “visiting” node and subtree.
    • 1 When helper node is not null, we should traverse the subtree, so we push helper and we go left
    • 2 When helper is null, means the left subtree of the roots finished, the root is the top element in the stack. We can print the top, and let helper = top.right.(traverse the left subtree firtst, then top. then right subtree)
    • 3 do 1 and 2 until helper is null and there is no nodes left in the stack
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
# 写法1.
class Solution(object):
    def inorderTraversal(self, root):
        if not root:
            return []
        res, stack = [], []
        cur = root
        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
        return res

# 写法2.
class Solution(object):
def inorderTraversal(self, root):
    if not root:
        return []

    stack, res = [], []
    cur = root
    while stack or cur:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            cur = stack.pop()
            res.append(cur.val)
            cur = cur.right
    return res

145. Binary Tree Postorder Traversal

Recursion

1
2
3
4
5
6
7
class Solution(object):
    def inorderTraversal(self, root):
        if not root:
            return []
        left = self.inorderTraversal(root.left)
        right = self.inorderTraversal(root.right)
        return left + right + [root.val]

Iteration

解法1. Two Stacks
  • left->right->root (reverse)=> root->right->left
  • Preorder -> Postorder
1
2
3
4
5
6
7
8
9
10
11
class Solution(object):
    def postorderTraversal(self, root):
        # Pre-order, but root->right->left
        stack, res = [root], []
        while stack:
            node = stack.pop()
            if node:
                res.append(node.val)
                stack.append(node.left)
                stack.append(node.right)
        return res[::-1]
  • What is the drawback of two stacks solution, if we deal with the nodes on the fly? (Online)
    Need to store everything in memory before we can get the whole post order traversal sequenct.
解法2. Stack + cur + prev

The problem is, we need to traverse both left and right subtrees first, then we can eliminate the root from the stack. We need an mechanism to know, when we finished visiting all subtrees’ nodes.

  • What we need to know?

    • Direction!!!!!!!
    • we are visiting down? or returning from left? or returning from right?

  • 思路1. 细分三种case
    The root is the top element in the stack
    Maintain a previous Node, to record the previous visiting node on the tracersing path, so that we know what the direction we are taking now and what is the direction we are taking next.

    • root = stack.top
    • if previous is null -> going down(left subtree has priority)
    • if previous is current’parent -> going down (left subtree has priority)
    • if previous == current.left -> left subtree finished, going current.right
    • if previous == current.right -> right subtree finished, pop current, going up.
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
55
56
57
58
59
60
61
# 思路写法
class Solution(object):
    def postorderTraversal(self, root):
        if not root:
            return []

        prev = None
        stack = [root]
        res = []
        while stack:
            cur = stack[-1]
            # Case1: 从父节点而来
            if not prev or cur == prev.left or cur == prev.right:
                if cur.left:
                    stack.append(cur.left)
                elif cur.right:
                    stack.append(cur.right)
                else: # 叶子节点
                    res.append(cur.val)
                    stack.pop()
            # Case2: 从左子树遍历完而来
            elif prev == cur.left:
                if cur.right:
                    stack.append(cur.right)
                else:
                    res.append(cur.val)
                    stack.pop()
            # Case3: 从右子树遍历完而来
            else:
                res.append(cur.val)
                stack.pop()
            prev = cur
        return res

# 简化写法
class Solution(object):
    def postorderTraversal1(self, root):
        if not root:
            return []

        prev = None
        stack = [root]
        res = []
        while stack:
            cur = stack[-1]
            # Case1: 从父节点而来
            if not prev or cur == prev.left or cur == prev.right:
                if cur.left:
                    stack.append(cur.left)
                elif cur.right:
                    stack.append(cur.right)
            # Case2: 从左子树遍历完而来
            elif prev == cur.left:
                if cur.right:
                    stack.append(cur.right)
            # Case3: 从右子树遍历完而来 或者 是叶子节点
            else:
                res.append(cur.val)
                stack.pop()
            prev = cur
        return res
  • 思路2 只划分上下两种case
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def postorderTraversal(self, root):
        if not root:
            return []

        prev = None
        stack, res = [root], []
        while stack:
            cur = stack[-1]
            # Case1: 什么时候访问节点？
            # 1.叶子节点 2.从子节点而来
            if (not cur.left and not cur.right) or (prev and (cur.right == prev or cur.left == prev)):
                node = stack.pop()
                res.append(node.val)
                prev = node
            # Case2: 从父节点而来
            else:
                if cur.right:
                    stack.append(cur.right)
                if cur.left:
                    stack.append(cur.left)
        return res
  • 什么时候访问root节点？
    • preorder: 直接访问 stack
    • inorder: 左subtree访问完了，再访问 stack+cur
    • postorder: 左右subtree访问完了，再访问 stack+cur+prev

590. N-ary Tree Postorder Traversal

  • Recursion
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def postorder(self, root):
        res = []
        self.dfs(root, res)
        return res

    def dfs(self, root, res):
        if not root:
            return

        for child in root.children:
            self.dfs(child, res)

        res.append(root.val)
  • Iteration
    Use ‘Two Stack’ Postorder Traversal Way!
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def postorder(self, root):
        if not root:
            return []

        res = []
        stack = [root]
        while stack:
            node = stack.pop()
            res.append(node.val)
            for child in node.children:
                stack.append(child)
        return res[::-1]

589. N-ary Tree Preorder Traversal

1
2
3
4
5
6
7
8
9
10
11
12
13
# Iteration
class Solution(object):
    def preorder(self, root):
        if not root: return []

        stack = [root]
        res = []
        while stack:
            node = stack.pop()
            res.append(node.val)
            for child in node.children[::-1]:
                stack.append(child)
        return res

Morris Traversal

  • 1968年，Knuth提出说能否将该问题的空间复杂度压缩到O(1)，同时原树的结构不能改变。

  • 大约十年后，1979年，Morris在”Traversing Binary Trees Simply and Cheaply”这篇论文中用一种Threaded Binary Tree的方法解决了该问题。

  • Morris算法在遍历过程中动态的构建Threaded Binary Tree，同时在结束时又将树恢复原样，在满足O(1)空间复杂度的同时也恰好满足Knuth对树结构不能改变的要求。适合空间复杂度要求高的场合！

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
# Inorder Demo Morris Traversal
class Solution(object):
    def inorderTraversal(self, root):
        if not root:
            return []
        res = []
        cur = root
        while cur:
            if not cur.left:
                res.append(cur.val)
                cur = cur.right
            else:
                # 1 Find Inorder Predecessor of cur
                prev = cur.left
                while prev.right and prev.right != cur:
                    prev = prev.right

                # 2 Connect or Restore the Pointer
                if not prev.right:
                    prev.right = cur
                    cur = cur.left
                else:
                    prev.right = None
                    res.append(cur.val)
                    cur = cur.right
        return res
Share