Long Luo's Life Notes

By Frank Luo

The Tree Traversal Algorithms are used to traversal the tree including Binary Tree and N-ary Tree.

1. Binary Tree Traversal

94. Binary Tree Inorder Traversal 144. Binary Tree Preorder Traversal 145. Binary Tree Postorder Traversal

2. N-ary Tree Traversal

589. N-ary Tree Preorder Traversal 590. N-ary Tree Postorder Traversal

Binary Tree

PreOrder

Algorithm Preorder(tree) 1. Visit the root; 2. Traverse the left subtree, i.e., call Preorder(left-subtree); 3. Traverse the right subtree, i.e., call Preorder(right-subtree).

Recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    preOrder(root, ans);
    return ans;
}

public void preOrder(TreeNode root, List<Integer> list) {
    if (root == null) {
        return;
    }
    
    list.add(root.val);
    preOrder(root.left, list);
    preOrder(root.right, list);
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(n)\)

Iteration

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    if (root == null) {
        return ans;
    }
    while (root != null || !stack.empty()) {
        while (root != null) {
            stack.push(root);
            ans.add(root.val);
            root = root.left;
        }
        
        root = stack.pop();
        root = root.right;
    }
    
    return ans;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(n)\)

By Long Luo

This article is the solution The XOR Cheat Sheet and Bit Manipulation with Easy Detailed Explanation of Problem 136. Single Number .

To solve this problem, there are serval solutions. However, the best method is using XOR.

we have this XOR cheatsheet:

1
2
3
4
5

1.  Zero Law: a XOR a = 0
2.  a XOR 0 = a
3.  a XOR b = b XOR a
4.  a XOR b XOR c = a XOR (b XOR c) = (a XOR b) XOR c
5.  a XOR b XOR a = b

According to the Zero law, all the numbers appears twice will be \(0\), and the single one will remain.

So code as follow:

By Long Luo

Imagine you’re asked a seemingly simple interview question:

Given an integer \(n\), return the \(n\)th Fibonacci number.

Most developers would immediately write the classic recursive solution. It is elegant, closely mirrors the mathematical definition, and can be implemented in just a few lines of code.

Unfortunately, it is also surprisingly inefficient.

What appears to be a trivial recurrence relation turns out to be an excellent case study in algorithm design. The same problem can be solved in many different ways, with running times ranging from exponential complexity all the way down to logarithmic complexity.

Along the way, we’ll encounter some of the most important ideas in computer science, including recursion, memoization, dynamic programming, divide-and-conquer, matrix exponentiation, and closed-form mathematical formulas.

In this article, we’ll explore nine different algorithms for computing Fibonacci numbers and see how each improvement reduces the amount of work required from \(O(\varphi^n)\) to \(O(n)\) and ultimately to \(O(\log n)\) .

Fibonacci Sequence

The \(\textit{Fibonacci Sequence}\)¹ are the numbers in the following integer sequence:

\[ 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, \dots. \]

By Long Luo

This article is the solution 2 Approaches: Base Conversion from High to Low and from Low to High of Problem 171. Excel Sheet Column Number.

Intuition

Basiclly, It’s base conversion.

We are familiar base \(10\). How do we calculate a number?

From high to low, starting with \(ans\) as \(0\), update \(ans\) with the current digit value each time, the update rule is \(ans = ans \times 10 + val\).

If there is a decimal number, encoded as \(\textit{ABC}\) not the arabic number, what’s it?

1
2
3
4

ans = 0
ans = ans * 10 + 1  => A
ans = ans * 10 + 2  => B
ans = ans * 10 + 3  => C

The answer is: \(123\).

from High to Low

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public int titleToNumber(String columnTitle) {
    int n = columnTitle.length();
    int ans = 0;
    int base = 1;
    for (int i = n - 1; i >= 0; i--) {
        int temp = 0;
        if (columnTitle.charAt(i) == 'Z') {
            temp = 26;
        } else {
            temp = columnTitle.charAt(i) - 'A' + 1;
        }
        ans = ans + base * temp;
        base *= 26;
    }

    return ans;
}

By Long Luo

This article is the solution 3 Approaches: Brute Force, HashMap and Sliding Window of Problem 219. Contains Duplicate II.

Here are \(3\) approaches to solve this problem in Java, which is Brute Force, HashMap and Sliding Window.

Brute Force

Easy, using \(2\) loops to determine whether there is the same number.

obviously, it will time out.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public boolean containsNearbyDuplicate(int[] nums, int k) {
    if (nums == null || nums.length <= 1 || k <= 0) {
        return false;
    }

    int len = nums.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (nums[i] == nums[j]) {
                if (Math.abs(i - j) <= k) {
                    return true;
                }
            }
        }
    }

    return false;
}

Analysis

• Time Complexity: \(O(n^2)\)
• Space Complexity: \(O(1)\)

HashMap

We use a \(\texttt{HashMap}\) to record the maximum index of each element. When scanning the array from left to right, the process:

• If an element \(\textit{nums}[i]\) already exists in the hash table and the index \(j\) of the element recorded in the hash table satisfies \(abs(i - j) \le k\), return \(\text{true}\);

• Recording \(\textit{nums}[i]\) and index \(i\) into the hash table, where \(i\) is the largest index of \(\textit{nums}[i]\).

The order of the above two-step operations cannot be changed, when the index \(i\) is traversed, the element equal to the current element and the maximum index of the element can only be found in the elements before the index \(i\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public boolean containsNearbyDuplicate(int[] nums, int k) {
    if (nums == null || nums.length <= 1 || k <= 0) {
        return false;
    }

    int len = nums.length;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < len; i++) {
        if (map.containsKey(nums[i])) {
            int idx = map.get(nums[i]);
            if (Math.abs(i - idx) <= k) {
                return true;
            }
            map.put(nums[i], i);
        } else {
            map.put(nums[i], i);
        }
    }

    return false;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(n)\)