Daily Sign Fri, June 30

Leetcode206

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
// Time: O(n) Space: In-place
public class Solution {
    public ListNode reverseList(ListNode head) {
        /**
         * Itervative version
         *
        ListNode prev = null;
        ListNode curr = head;
 
        while(curr != null){
            ListNode temp = curr.next;
            curr.next = prev;
            prev= curr;
            curr = temp;
 
        }
 
        return prev; */ 
 
        if(head == null) return null;
 
        return helper((ListNode) null, head);
    }
 
    public ListNode helper(ListNode curr, ListNode next){
        ListNode temp = next.next;
        next.next = curr;
        if(temp != null){
            return helper(next, temp);
        }
        return next;
    }
}

Leetcode138. Another better solution is posted here.

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
62
63
64
65
66
67
68
69
70
71
/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
 //Time: O(n^2) Space: O(n)
 //Naive solution
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head == null) return null;
 
        //get the length of orginal list 
        int length = 0;
        RandomListNode oldnode = head;
        while(oldnode != null){
            length ++;
            oldnode = oldnode.next;
        }
 
        // create an array which records new list node
        RandomListNode[] array = new RandomListNode[length +1];
 
        RandomListNode newhead = new RandomListNode(head.label);
        RandomListNode node = newhead;
        oldnode = head;
 
        //copy all nodes( next and label)
        int index = 0;
        while(oldnode.next!=null){
            node.next = new RandomListNode(oldnode.next.label);
            array[index] = node;
            index ++;
            node = node.next;
            oldnode = oldnode.next;
        }
 
        // the last element is eliminated in the above process and add them 
        array[index] = node;
        index ++;
        array[index] = null;
 
        // copy all remdom pointers
        // with index to get the new node location
        node = newhead;
        oldnode = head;
        while(node != null){
            node.random = array[indexof(oldnode, head)];
            oldnode = oldnode.next;
            node = node.next;
        }
 
        return newhead;
 
 
 
    }
 
    // get the index of random node in orginal list
    public int indexof(RandomListNode node, RandomListNode head){
        int index = 0;
        while(head != null && head != node.random){
            head= head.next;
            index ++;
        }
        return index;
 
    }
}

Leetcode419. A better solution can be found here!

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
/**
 * Time O(n^2), Space O(1)
 * Modify the board and compress all battleships to one node!
 */
public class Solution {
    public int countBattleships(char[][] board) {
        int count = 0;
        for(int i=0; i< board.length; i++){
            for (int j=0; j< board[0].length; j++){
                if(board[i][j] == 'X'){
                    if (check(board,i,j)){
                        board[i][j] = '.' ;
                    }else{
                        count ++;
                    }
                }
            }
        }
        return count;
    }
 
    public boolean check(char[][] board, int i, int j){
        boolean h = false;
        boolean v = false;
 
        if(0 < i && (i < board.length-1)){
            h = (board[i-1][j] == 'X') || (board[i+1][j]== 'X') ;
        }else if(i == 0 && (i < board.length-1) ){
            h = board[i+1][j] == 'X';
        }else if((i == board.length-1) && i >0){
            h = board[i-1][j] == 'X';
        }
 
        if(0 < j && (j < board[0].length-1)){
            v = (board[i][j-1] == 'X') || (board[i][j+1]== 'X') ;
        }else if(j == 0 && (j < board[0].length-1) ){
            v = board[i][j+1] == 'X';
        }else if((j == board[0].length-1) && j >0){
            v = board[i][j-1] == 'X';
        }
 
        return h || v;
    }
}

Leetcode273

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
public class Solution {
    static String[] units ={"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine" };
    static String[] ten  ={"Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen" };
    static String[] tens  ={"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety" };
    static String[] digits = {"", "Thousand ", "Million ", "Billion "};
 
    public String numberToWords(int num) {
        if(num ==0) return "Zero";
        StringBuilder sb = new StringBuilder();
        int index =0;
        while(num > 0){
            if(num%1000 > 0)
            	sb.insert(0, threedigits(num%1000) + digits[index]);
            index ++;
            num /= 1000;
        }
        String a = sb.toString();
        return a.substring(0, a.length()-1);
    }
 
    public String threedigits(int num){
        StringBuilder sb = new StringBuilder();
        if(num >= 100){
            sb.append(units[num/100] + " Hundred ");
 
            num = num % 100;
        }
        if(num >=20){
            sb.append(tens[num/10] +" ");
            num = num %10;
        }
        if(num >=10){
            sb.append(ten[num%10] +" ");
            return sb.toString();
        }
        if(num > 0){
            sb.append(units[num]+" ");
            // return sb.toString();
        }
        return sb.toString();
    }
}

Leetcode54

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
/**
 *
 * This is method is got from my previous submission.
 * Time: O(n) Space: O(1)
 *
 */
public class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> list = new ArrayList<Integer>();
        if(matrix.length == 0) return list;
        int m = matrix.length;
        int n = matrix[0].length;
        int rowtop = 0;
        int rowbottom = m-1;
        int columnleft =0;
        int columnright = n-1;
 
        while(rowtop<=rowbottom && columnleft<=columnright){
            for(int i = columnleft; i<= columnright; i++ ){
                list.add(matrix[rowtop][i]);
            }
            rowtop ++;
 
            for(int i = rowtop; i<= rowbottom; i++ ){
                list.add(matrix[i][columnright]);
            }
            columnright --;   
 
            if(rowtop <= rowbottom){
            for(int i = columnright; i>= columnleft; i-- ){
                list.add(matrix[rowbottom][i]);
            }
            rowbottom --;
            }
 
            if(columnleft <= columnright){
            for(int i = rowbottom; i>= rowtop; i-- ){
                list.add(matrix[i][columnleft]);
            }
            columnleft ++; 
            }
 
 
        }
 
        return list;
    }
}

Leetcode171

1
2
3
4
5
6
7
8
9
public class Solution {
    public int titleToNumber(String s) {
        int sum = 0;
        for(int i=0; i< s.length(); i++){
            sum = sum * 26 + (s.charAt(i) - 'A' +1);
        }
        return sum;
    }
}

Leetcode235

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
/**
 *
 * This is method is got from my previous submission.
 * DFS Method
 * Time: O(n) Space: in-place
 *
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if((p.val - root.val)*(root.val -q.val) >= 0) return root;
        if(p.val<root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);
        if(p.val>root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);
        return null;
    }
}

Leetcode200

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
/**
 *
 * Also DFS Method
 * Time: O(m * n) , generally, we can consider we have visited each element once
 *
 */
public class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i=0; i< grid.length; i++){
            for (int j=0; j< grid[0].length; j++){
                if(grid[i][j] == '1'){
                    explore(grid, i, j);
                    count++;
                }
            }
        }
        return count;        
    }
 
    public void explore(char[][] grid, int i, int j){
        if(grid[i][j] == '0'){
            return;
        }else{
            grid[i][j] = '0';
        }
 
        if(i > 0)
            explore(grid, i-1,j);
        if(i < grid.length -1)
            explore(grid, i+1,j);
        if(j > 0)
            explore(grid, i, j-1);
        if(j < grid[0].length -1)
            explore(grid, i, j+1);
    }
}

Leetcode88

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
/**
 *
 * Time: O(m + n) 
 *
 */
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int end1 = m-1;
        int end2 = n-1;
        int end = m+n -1;
 
        while(end1>=0 && end2 >=0){
            nums1[end--] = nums1[end1] > nums2[end2] ? nums1[end1--]:nums2[end2--];
        }
 
        while(end2 >= 0){
            nums1[end--] = nums2[end2--];
        }       
    }
}

Leetcode445

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
 
/**
 *
 * This solution is so tricky and is not recommended!
 * 1. Compute the length of lists O(2n)
 * 2. Find matching part of two list O(n)
 * 3. Recursion: compute add O(n)
 * 4. Recursion: compute non-matching part if there is carry bit O(n)
 * 5. Other decoration O(1)
 * DFS Method
 * Time: O(n) Space: approximately in-place
 *
 */
 
 
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int len1 =len(l1);
        int len2 = len(l2);
 
        if(len2 < len1){
            return add(l1,l2,len1,len2);
        }else{
            return add(l2,l1,len2,len1);
        }
 
 
    }
 
    public ListNode add(ListNode l1, ListNode l2, int len1, int len2){
        ListNode head = l1;
        for(int i = len2; i != len1; i++){
            l1=l1.next;
        }
        int add = helper(l1,l2);
        if(add == 0){
  	    return head;              
        }else{
            if(len1 == len2){
                ListNode dummy = new ListNode(1);
                dummy.next = head;
                return dummy;
            }else{
                ListNode ptr = head;
                int add2 =  helper2(ptr, l1);
                if(add2 ==1){
                  	ListNode dummy = new ListNode(1);
                	dummy.next = head;   
                    return dummy;
                }else{
                    return head;
                }
            }
        }    
    }
 
    public int helper(ListNode l1, ListNode l2){
        int add = 0;
        if(l1.next != null && l2.next != null){
            add=helper(l1.next, l2.next);
        }
        int newadd = (l1.val +l2.val + add) / 10;
        l1.val = (l1.val +l2.val + add) % 10;
        return newadd;
    }
 
    public int len(ListNode l1){
        int len = 0;
        while(l1 != null){
            l1 = l1.next;
            len ++;
        }
        return len;
    }
 
    public int helper2(ListNode head, ListNode l1){
        int add = 1;
        if(head.next != l1){
            add=helper2(head.next, l1);
        }
      	int newadd = (head.val + add) / 10;
        head.val = (head.val + add) % 10;
        return newadd;        
    }
}

Ha! Joking LC~

Have you even known longest uncommon substring? Leetcode521 can tell you what LUCS…

In this condition, do you know what LUCS of “acd” and “cd”? It is “acd”, which means the longer one is always LUCS. When string a and b have equal length, if they are completely same, there is no LUCS while if not, the lUCS is either string a or b.

Start Your Junit in Mac OS

After struggle of half a day, I can finally begin my Junit test with terminal in Mac OS. Before you set up your environment, you can refer the official site , which is a brilliant guide.

1. Download Junit
Go to official site and get two .jar file:
junit.jar
hamcrest-core.jar

2. Generally, I put all my jars in ~/java/package, you can easily use cp or mv in terminal.

cp ~/Downloads/hamcrest-core-1.3.jar ~/java/package
cp ~/Downloads/junit-4.12.jar ~/java/package

3. Set up classpath
Open bash profile and add following lines. Notice: you may modify the actual file location.

# Junit test 
export CLASSPATH=~/java/package/junit-4.12.jar:$CLASSPATH
export CLASSPATH=~/java/package/hamcrest-core-1.3.jar:$CLASSPATH

4. Create a new sort.java file in test folder and append the following lines

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
// Merge sort of array
public class sort{
 
	public void mergesort(int[] array){
		int low = 0;
		int high = array.length;
		sortHelper(low, high -1, array);
	}
 
	public void sortHelper(int low, int high, int[] array){
		if(low < high){
			int pivot = low + (high - low)/2;
 
			sortHelper(low, pivot, array);
			sortHelper(pivot + 1 ,high, array);
 
			merge(low, pivot, high, array);
		}
	}
 
 
	public void merge(int low, int pivot, int high, int[] array){
		int[] helper = new int[high + 1];
		for(int i =low; i <=high; i++){
			helper[i] = array[i];
		} 
 
		int i = low;
		int j = pivot +1;
		int k = low;
 
		while(i <= pivot && j <= high){
			if(helper[i] <= helper[j]){
				array[k] = helper[i];
				i++;
			}else{
				array[k] = helper[j];
				j++;
			}
			k++;
		}
 
		while(i <= pivot){
			array[k] = helper[i];
			k++;
			i++;
		}
	}
}

4. Create a new sortTest.java test file in test folder and append the following lines

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;
 
import java.util.Arrays;
import java.util.Random;
 
import org.junit.Before;
import org.junit.Test;
 
public class sortTest {
 
    private int[] numbers;
    private final static int SIZE = 7;
    private final static int MAX = 20;
 
    @Before
    public void setUp() throws Exception {
        numbers = new int[SIZE];
        Random generator = new Random();
        for (int i = 0; i < numbers.length; i++) {
            numbers[i] = generator.nextInt(MAX);
        }
    }
 
    @Test
    public void testMergeSort() {
        long startTime = System.currentTimeMillis();
 
        sort sorter = new sort();
        sorter.mergesort(numbers);
 
        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println("Mergesort " + elapsedTime);
 
        for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i] > numbers[i + 1]) {
                fail("Should not happen");
            }
        }
        assertTrue(true);
 
    }
 
    @Test
    public void itWorksRepeatably() {
        for (int i = 0; i < 200; i++) {
            numbers = new int[SIZE];
            Random generator = new Random();
            for (int a = 0; a < numbers.length; a++) {
                numbers[a] = generator.nextInt(MAX);
            }
            sort sorter = new sort();
            sorter.mergesort(numbers);
            for (int j = 0; j < numbers.length - 1; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    fail("Should not happen");
                }
            }
            assertTrue(true);
        }
    }
 
    @Test
    public void testStandardSort() {
        long startTime = System.currentTimeMillis();
        Arrays.sort(numbers);
        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println("Standard Java sort " + elapsedTime);
 
        for (int i = 0; i < numbers.length - 1; i++) {
            if (numbers[i] > numbers[i + 1]) {
                fail("Should not happen");
            }
        }
        assertTrue(true);
    }
 
}

5. Compile with Javac

javac *.java 

6. Run test

java org.junit.runner.JUnitCore sortTest

If all tests pass, you will get such information in termianl:

JUnit version 4.12
.Mergesort 0
..Standard Java sort 1

Time: 0.006

OK (3 tests)

Recall: DP method Longest Common Subsequence

If you want to knwo LCS problem well, please refer wiki.

**Subsequence is different from substring**

Simply post code here(Java)!

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
public static String lcs(String a, String b) {
    int[][] lengths = new int[a.length()+1][b.length()+1];
 
    // row 0 and column 0 are initialized to 0 already
 
    for (int i = 0; i &lt; a.length(); i++)
        for (int j = 0; j &lt; b.length(); j++)
            if (a.charAt(i) == b.charAt(j))
                lengths[i+1][j+1] = lengths[i][j] + 1;
            else
                lengths[i+1][j+1] =
                    Math.max(lengths[i+1][j], lengths[i][j+1]);
 
    // read the substring out from the matrix
    StringBuffer sb = new StringBuffer();
    for (int x = a.length(), y = b.length();
         x != 0 &amp;&amp; y != 0; ) {
        if (lengths[x][y] == lengths[x-1][y])
            x--;
        else if (lengths[x][y] == lengths[x][y-1])
            y--;
        else {
            assert a.charAt(x-1) == b.charAt(y-1);
            sb.append(a.charAt(x-1));
            x--;
            y--;
        }
    }
 
    return sb.reverse().toString();
}

Read More

Layer Traversal of Tree — Special Example

This problem is referred from Leetcode515.

This is a typical problem which use layer traversal of tree. How to implement such traversal?

Generally, we can use BFS for implementation. It is an amazing example for BFS!

Specially, I want to introduce DFS idea for this problem.

Firstly, we maintain a list with max size is tree depth and use traversal with depth record to fill out this list. When we use any traversal method and walk all though, we can get the final result.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public List largestValues(TreeNode root) {
        List list = new LinkedList();
        traversal(list, root, 0);
        return list;
    }
 
    public void traversal(List list, TreeNode node, int depth){
        if(node == null) return;
 
        if(depth == list.size()){
            list.add(node.val);
        }else{
            list.set(depth, Math.max(list.get(depth), node.val));
        }
 
        traversal(list, node.left, depth+1);
        traversal(list, node.right, depth+1);
    }
}

Reverse In-order Traversal of BST

This problem is referred from Leetcode538.
Generally, in-order traversal is a left-root-end traversal, while this problem requires us to implement s right-root-left traversal? We can easily implement an iterative or recursive version, when at the same time, we maintain an variable to record the current sum value during traversal.
Attention: It is key to implement a real reversed in-order traversal of BST.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public TreeNode convertBST(TreeNode root) {
        int sum = 0;
        add(root, sum);
        return root;
    }
 
    public int add(TreeNode node, int sum){
        if(node == null) return sum;
        sum = add(node.right, sum);
        node.val += sum;
        sum = node.val;
        sum = add(node.left, sum);
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// This is an iterative version with stack
public TreeNode ConvertBST(TreeNode root) {
    TreeNode node = root;
    Stack<TreeNode> stack = new Stack<TreeNode>();
 
    int sum = 0;
    while (node != null || stack.Count > 0)
    {
        if (node != null)
        {
            stack.Push(node);
            node = node.right;
        }
        else
        {
            node = stack.Pop();
            sum += node.val;
            node.val = sum;
 
            node = node.left;
        }
    }
 
    return root;
}

hierarchical traversal application

The problem is referred from leetcode117!

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
/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
public class Solution {
 
    //based on level order traversal
    public void connect(TreeLinkNode root) {
        TreeLinkNode head = null;
 
        TreeLinkNode curr = root;
        TreeLinkNode prev = null;
 
        while(curr != null){
            // Check if travesal reach last level of tree
 
            while(curr != null){
                // Check if traversal reach end of this level 
 
                if (curr.left != null){
                    if(head == null){
                        head = curr.left;
                    }else{
                        prev.next = curr.left;
                    }
                    prev = curr.left;
                }
 
                if (curr.right != null){
                    if(head == null){
                        head = curr.right;
                    }else{
                        prev.next = curr.right;
                    }
                    prev = curr.right;
                }
 
                curr = curr.next;
            }
 
            curr =  head;
            head = null;
            prev = null;
        }
    }
}
Generally, it seems I can use stack to solve the BFS traversal of tree; however, I cannot detect if I have finished traverse one level. In this problem, subtle link in this link-tree help us traverse the higher level, in other words, we do not need to record the traversed level information.

Overall, the time complexity is this solution is O(n) and space complexity is O(1), while in fact, this algorithm is in-place.

Read More

Sort Methods

I am ashamed that I even cannot finish such an easy sublet like quick sort! I decide to take two days to summarize intermediate sort methods in Java.

QuickSort

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
public void quicksort(int[] values) {
    // check for empty or null array
    if (values ==null || values.length==0){
        return;
    }
    quicksorthelper(0,  values.length - 1);
}
 
private void quicksorthelper(int low, int high) {
    int i = low, j = high;
    int pivot = numbers[low + (high-low)/2];
 
    while (i &lt;= j) {
        while (numbers[i] &lt; pivot) { i++; } while (numbers[j] &gt; pivot) {
            j--;
        }
        if (i &lt;= j) {
            exchange(i, j);
            i++;
            j--;
        }
    }
    if (low &lt; j)
        quicksort(low, j);
    if (i &lt; high)
        quicksort(i, high);
}
 
private void exchange(int i, int j) {
    int temp = numbers[i];
    numbers[i] = numbers[j];
    numbers[j] = temp;
}

Keyword-Final

It is a shame that I was so confused with such basic concept. Now I am clarifying some concepts for final.

1. Final references:

1
2
3
final LinkedList list = new LinkedList();
list.add(1);
assertEquals(1, list.pop());

The test will pass for the object in heap can be changed however, the reference cannot be changed. For example,

1
2
final LinkedList list = new LinkedList();
list = new LinkedList();

This sublet cannot be compiled for the reference cannot be changed.

2. Final method
3. Final class
4. Final parameter

Inorder Tree Traversal

CN: 二叉树的中序遍历

Generally, there are two main methods for in-order tree traversal, iterative and recursive methods:

Recursive 

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();

        helper(root, res);
        return res;
    }

    private void helper(TreeNode root, List<Integer> res) {
        if (root != null) {
            if (root.left != null) {
                helper(root.left, res);
            }
            res.add(root.val);
            if (root.right != null) {
                helper(root.right, res);
           }
       }
    }
}

Iterative 

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
    
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode cur = root;
    
        while(cur!=null || !stack.empty()){
            while(cur!=null){
                stack.add(cur);
                cur = cur.left;
            }
            cur = stack.pop();
            list.add(cur.val);
            cur = cur.right;
        }
    
        return list;
    }
}

Generally for the above methods, the time complexity is o(n), and the space complexity is also o(n). Another modified version is come up with:

Morris traversal

The space complexity is just o(1).

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return new ArrayList<Integer>();
        List<Integer> res = new ArrayList<Integer>();
        TreeNode pre = null;
        while(root != null){
        	if(root.left == null){
        		res.add(root.val);
        		root = root.right;
        	}else{
        		pre = root.left;
        		while(pre.right != null && pre.right != root){
        			pre = pre.right;
        		}
        		if(pre.right == null){
        			pre.right = root;
        			root = root.left;
        		}else{
        			pre.right = null;
        			res.add(root.val);
        			root = root.right;
        		}
        	}
        }
        return res;
    }
}

The original problem is referred from leetcode94, also, some pseudo code and algorithm descriptions can be get on wiki.