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

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\)

We can see the fibonacci series seqences in the natrual world like the sunflower, the nautilus and the galaxy.

In mathematical terms, the sequence \(F(n)\) of Fibonacci numbers is defined by the recurrence relation

\[ F(n) = F(n-1) + F(n-2) \]

with seed values \(F(0) = 0\) and \(F(1) = 1\).

The Fibonacci sequence is often used in introductory computer science courses to explain recurrence relations, dynamic programming, and proofs by induction. Because the Fibonacci sequence is central to several core computer science concepts, the following programming problem has become fairly popular in software engineering interviews.

Given an input \(n\), return the \(nth\) number in the Fibonacci sequence.

Below I’ve listed \(9\) approaches to this problem. These different solutions illustrate different programming and algorithmic techniques that can be used to solve other problems. You’ll notice that many of these solutions build from previous solutions.

Solution 1 Lookup Table - 32 bit signed integers only

If we don’t need to solve very large values and are time-sensitive, we can calculate all values in advance.

This function will work strictly in the case that we’re dealing with \(32\) bit signed integers (which could be a constraint in languages like Java, C/C++, etc.)

The Fibonacci sequence grows very quickly. So fast, that only the first \(47\) Fibonacci numbers fit within the range of a \(32\) bit signed integer. This method requires only a quick list lookup to find the nth Fibonacci number, so it runs in constant time. Since the list is of fixed length, this method runs in constant space as well.

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

class Solution {
    int[] fib_nums = {
            0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
            6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040,
            1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986,
            102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903
    };

    public int fib(int n) {
        return fib_nums[n];
    }
};

Analysis

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

Solution 2 Recursion

A simple method that is a direct recursive implementation mathematical recurrence relation is given above.

1
2
3
4
5
6
7
8

//Fibonacci Series using Recursion
public static int fib(int n) {
	if (n <= 1) {
		return n;
	}

	return fib(n - 1) + fib(n - 2);
}

Analysis

• Time Complexity: \(O(\phi^n)\), where \(\phi\) is the golden ratio (\(\phi \simeq 1.618...\)).

If we count the number of calls that this algorithm makes for any n, we will find its runtime complexity.

Let \(T(n)\) refer to the number of calls to fib1 that are required to evaluate fib1(n).

When fib1(0) or fib1(1) is called, fib1 doesn’t make any additional recursive calls, so \(T(0)\) and \(T(1)\) must equal 1.

For any other n, when fib1(n) is called, fib1(n - 1) and fib1(n - 2) are also called.

So

\[ T(n) = 1 + T(n - 1) + T(n - 2) \]

Using more advanced mathematical techniques, like generating functions, one can solve the recurrence \(T\), and find that \(T\) scales as \(O(\phi)\).

If the original recursion tree were to be implemented then this would have been the tree but now for n times the recursion function is called.

Original tree for recursion:

1
2
3
4
5
6
7
8
9

                          fib(5)   
                     /                \
               fib(4)                fib(3)   
             /        \              /       \ 
         fib(3)      fib(2)         fib(2)   fib(1)
        /    \       /    \        /      \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /     \
fib(1) fib(0)

Optimized tree for recursion for code above:

1
2
3
4
5

fib(5) 
fib(4)
fib(3)
fib(2)
fib(1)

• Space Complexity: \(O(n)\) if we consider the function call stack size, otherwise \(O(1)\).

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)\)