LeetCode 4. Median of Two Sorted Arrays [Hard] [C++] 解題筆記

這題給定兩個排序好的 array nums1 和 nums2，其長度分別為 m, n，要求我們在 O(log(m+n)) 的時間複雜度限制內找出這兩個 array 合併後的中位數。

EX:

        nums1 = [1, 3]

        nums2 = [2]

    The median is 2.0

LeetCode 99. Recover Binary Search Tree [Hard] [C++] 解題筆記

這題給我們一個錯的 binary tree (tree 的某兩個 node 被交換了導致該 tree 不符合 binary tree 的性質)，要求我們修正這個 tree 並不改變其結構。

EX:

        Input: [3,1,4,null,null,2]

      3
     / \
    1   4
       /
      2

    Output: [2,1,4,null,null,3]

      2
     / \
    1   4
       /
      3

Morris Traversal [Algorithm] 演算法筆記

問題:

        Morris Traversal 主要解決的是 binary tree traversal 的問題，講到 binary tree traversal，一般人直覺就會想到可以做 preorder, inorder, postorder traversal 求解，但是上述方法一般的實作方式(recursive or iterative + stack) 其 空間複雜度皆為 O(n)，原因是我們必須要紀錄尚未走訪的 node，例如在 inorder traversal 中，我們先照著 左子樹-> root ->右子樹的順序遍歷，如果不用 stack 紀錄 root，當我們走訪完左子樹之後就無法回到 root 繼續走訪。那要怎摸在不使用 stack (額外空間) 的情況下完成 traversal 呢？ Morris Traversal 正是為此而生，它可以在 O(1) space 情況下同樣達到 O(n) 時間複雜度完成 traversal。

LeetCode 100. Same Tree [Easy] [C++] 解題筆記

給我們兩個 binary tree，要我們判斷兩者是不是一樣的。

EX:

        Input:    1          1

                      / \        / \
                   2   1     1   2

                 [1,2,1],   [1,1,2]

        Output: false

LeetCode 98. Validate Binary Search Tree [Medium] [C++] 解題筆記

這題要我們判斷一個 binary tree 是不是 binary search tree。

EX:

         5

       /   \
      1   4
      / \
    3   6

Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

LeetCode 95. Unique Binary Search Trees II [Medium] [C++] 解題筆記

這題給我們一個數字 n 要我們列舉出所有 1 ... n 的數可以形成的 unique binary search tree.

EX:

      Input: 3

      Output:
    [
      [1,null,3,2],
      [3,2,null,1],
      [3,1,null,null,2],
      [2,1,3],
      [1,null,2,null,3]
    ]
  Explanation:
  The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \         /     /        / \      \
     3     2     1      1   3      2
    /       /       \                    \
   2     1         2                   3

LeetCode 96. Unique Binary Search Trees [Medium] [C++] 解題筆記

這題要我們求數字 1~n 可以形成的 unique binary tree 的個數。

EX:

        Input: 3

       Output: 5
 

Explanation:
Given n = 3, there are a total of 5 unique BST's:

       1         3     3      2      1
        \        /      /        / \      \
         3     2     1      1   3      2
        /      /        \                     \
       2     1         2                    3

LeetCode 94. Binary Tree Inorder Traversal [Medium] [C++] 解題筆記

這題要我們找一個 Tree 的中序排序。

EX:

        Input: [1,null,2,3]

       1
        \
         2
        /
       3

       Output: [1,3,2]

LeetCode 93. Restore IP Addresses [Medium] [C++] 解題筆記

這題給定一個只由數字組成的 string s，要我們求 s 可能形成的所有合法的 IP address。

EX:

        Input: "25525511135"

    Output: ["255.255.11.135", "255.255.111.35"]

LeetCode 206. Reverse Linked List [Easy] [C++] 解題筆記

這題要求我們反轉一個 Single Linked List.

EX:

        Input: 1->2->3->4->5->NULL

        Output: 5->4->3->2->1->NULL

LeetCode 91. Decode Ways [Medium] [C++] 解題筆記

這題給定一個都是數字的非空字串 s，每個數字可以對應到一個 A~Z 的字母，要我們求共有多少種解碼方式。

EX:

        'A' -> 1

        'B' -> 2
        ...
        'Z' -> 26

input:

        "226"

Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

LeetCode 90. Subsets II [Medium] [C++] 解題筆記

這題算是 78. Subsets 的延伸題，一樣給定一個 array，其中數字可能重複，要我們求 array 中所有數字可以組成的不重複子集。

EX:

        Input: [1,2,2]

       Output:
        [
          [2],
          [1],
          [1,2,2],
          [2,2],
          [1,2],
          []
        ]

LeetCode 88. Merge Sorted Array [Easy] [C++] 解題筆記

這題給定兩個在第 m 與第 n 個元素前已經排序好的陣列 nums1, nums2，要我們將兩個陣列合併到 nums1 中並排序好。(nums1 保證有足夠的空間存放 m + n)。

EX:

        nums1 = [4, 5, 6, 0, 0, 0]

        

        nums2 = [1, 2, 3]

Ans: nums1 = [1, 2, 3, 4, 5, 6]