Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

First solutions is bit manipulation.

If two numbers are the same, then XOR result is 0.

And for negative integers:

A negative number is a bit field just like a positive number. XOR doesn’t care

Follow-up question, what if the input is not an array in interger, but a bunch of Strings? This guy have the answer.

There are ways of XORing strings by XORing the individual chars - you would just have to have a temporary variable as large as the largest string.

What wouldn’t work is trying to XOR a linked list or some other complicated data structure.

Which is to say, a string is just like an array of chars (integers). For every char (integer), just apply the same method and we shall have the answer.

Second solution is HashSet, but must use more space. Code is posted below as well.

Someone also sort then find, but this takes more time.

Code

First, XOR solution

public int singleNumber(int[] A) {
    int num = A[0];
    for (int i = 1; i < A.length; i ++)
        num = num ^ A[i];
    return num;
}

Second, HashSet solution

The last line “return -1” is only for compiling purposes, and will not be executed.

public int singleNumber(int[] A) {
    HashSet<Integer> set = new HashSet<Integer>();
    for (int i = 0; i < A.length; i ++) {
        if (set.contains(A[i]))
            set.remove(A[i]);
        else
            set.add(A[i]);
    }
    for (Integer a: set)
        return a;
    return -1;
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a tough question, which requires a lot of math-related thinking.

My solution is IMHO very simple and easy. I first do a cumulation of gas from beginning to the end, and find the lowest cumulative value of the gas tank (of course can be negative). That point is where I start the journey, which is to say, I will validate the path from that point, and then return the result.

This idea is not seen on Internet, although it is just 2 loops thru the list, and time complexity is also O(n). Anyway, there’s a great solution which most people uses.

There’s a great post that gives 2 valid conclusions:

1. If car starts at A and can not reach B (let’s say B is the first station that A can not reach), then any station between A and B can not reach B.
2. If the total number of gas is bigger than the total number of cost. There must be a valid solution.

From here, a great solution can be found.

Solution

A very detailed explanation and code is found from this blog.

1. 从i开始，j是当前station的指针，sum += gas[j] – cost[j] （从j站加了油，再算上从i开始走到j剩的油，走到j+1站还能剩下多少油）
2. 如果sum < 0，说明从i开始是不行的。那能不能从i..j中间的某个位置开始呢？假设能从k (i <=k<=j)走，那么i..j < 0，若k..j >=0，说明i..k – 1更是<0，那从k处就早该断开了，根本轮不到j。
3. 所以一旦sum<0，i就赋成j + 1，sum归零。

And note that if i is moved to j, there is no need to check (0..old_i) again, because this range must be reachable (write code again for beter understanding).

Coding this solution is not easy! I failed to do it.

Code

First, my solution

public int canCompleteCircuit(int[] gas, int[] cost) {
    int len = gas.length;
    if (len == 0) return -1;
    int start = -1, min = Integer.MAX_VALUE, total = 0;
    for (int i = 0; i < len; i ++) {
        total += getDiff(gas, cost, i);
        if (total < min) {
            min = total;
            start = i;
        }
    }
    start = (start + 1) % len;
    // now traverse the route from start 
    total = 0;
    for (int i = 0; i < len; i ++) {
        total += getDiff(gas, cost, (start + i) % len);
        if (total < 0) return -1; 
    }
    return start;
}

private int getDiff(int[] gas, int[] cost, int i) {
    return gas[i] - cost[i];
}

Second, best solution

public int canCompleteCircuit(int[] gas, int[] cost) {
    int i = 0, j = 0;
    int sum = 0;
    int total = 0;
    while (j < gas.length) {
        int diff = gas[j] - cost[j];
        if (sum + diff < 0) {
            i = j + 1;
            sum = 0;
        } else {
            sum += diff;
        }
        j++;
        total += diff;
    }
    return total >= 0 ? i : -1;
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a difficult question.

Directly doing it will result in a lot of trace-backs. The following picture gives a clear idea of what the problem is:

When traversing from low to high (upward sloping), just increase candy, that’s fine. But when sloping down, we would have no idea what value to set until we reach the min point. Fish Lei have a good solution of “trace-back algorithm” to re-adjust the values by traversing back to the top again.

However, I personally think the 2nd solution is way more splendid, that I will not cover 1st solution in detail.

Solution

The 2nd solution is very similar to “Trapping Rain Water”. This blog is the best explanation I found from Internet.

1. For the first time, scan from left to right. If current rating is larger than the left one, give one more candy to current child than the left one.
2. For the second time, scan from right to left. If current rating is larger than the right one, give one more candy to current child than the right one.

We consider the policy as two folds, left policy and right policy. Left policy means a child has more candies than his left one if his rating is higher than his left one. The first scan ensures that the distribution meets left policy. The second scan ensures that the distribution meets right policy. However, it will not violate left policy.

Code

2nd solution

public int candy(int[] ratings) {
    int len = ratings.length;
    if (len <= 1) return len;
    int[] candy = new int[len];
    candy[0] = candy[len-1] = 1;
    for (int i = 1; i < len; i ++) {
        if (ratings[i] > ratings[i-1])
            candy[i] = candy[i-1] + 1;
        else candy[i] = 1;
    }
    for (int i = len-2; i >= 0; i --) {
        if (ratings[i] > ratings[i+1])
            candy[i] = Math.max(candy[i], candy[i+1] + 1);
    }
    int sum = 0;
    for (int i = 0; i < len; i ++) sum += candy[i];
    return sum;
}

Question

link

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an unsolvable question.

Solution

A solution is available here, but I did not solved it and I gave up.

Code

public class Node {  
    public int dist;  
    public String str;  
    public LinkedList<Node> prev;  

    public Node(int dist, String str) {  
        this.dist = dist;  
        this.str = str;  
        this.prev = new LinkedList<Node>();
    }

    public void addPrev(Node pNode) {  
        prev.add(pNode);  
    }  
}  

public ArrayList<ArrayList<String>> findLadders(String start,  
        String end, HashSet<String> dict) {  
    dict.add(end);  

    // Key: the dictionary string; Value: Node  
    Map<String, Node> map = new HashMap<String, Node>();  
    Queue<String> queue = new LinkedList<String>();  

    Node startNode = new Node(1, start);  
    queue.offer(start);  
    map.put(start, startNode);  

    ArrayList<ArrayList<String>> ret = new ArrayList<ArrayList<String>>();  

    while (!queue.isEmpty()) {  
        String str = queue.poll();  

        if (str.equals(end)) {  
            getPaths(map.get(end), map, new ArrayList<String>(), ret);  
            return ret;  
        }  

        for (int i = 0; i < str.length(); i++) {  
            for (int j = 0; j <= 25; j++) {  
                // transform it into another word  
                String newStr = replace(str, i, (char) ('a' + j));  

                // if a new word is explored  
                if (dict.contains(newStr)) {  
                    if (!map.containsKey(newStr)) {  
                        // construct a new node  
                        Node node = map.get(str);  
                        Node newNode = new Node(node.dist + 1, newStr);  
                        newNode.prev = new LinkedList<Node>();  
                        newNode.prev.add(node);  

                        map.put(newStr, newNode);  
                        queue.offer(newStr);  
                    } else {  
                        Node node = map.get(newStr);  
                        Node prevNode = map.get(str);  

                        // increase the path set  
                        if (node.dist == prevNode.dist + 1) {  
                            node.addPrev(prevNode);  
                            // queue.offer(newStr); // will cause TLE!!!  
                        }  
                    }  
                }  
            }  
        }  
    }  

    return ret; // return an empty set  
}  

// replace the index of the given string with the given char  
private String replace(String str, int index, char c) {  
    StringBuilder sb = new StringBuilder(str);  
    sb.setCharAt(index, c);  
    return sb.toString();  
}  

// get all the paths by using DFS  
private void getPaths(Node end, Map<String, Node> map,  
        ArrayList<String> curPath, ArrayList<ArrayList<String>> paths) {  
    if (end == null) {  
        paths.add(curPath);  
        return;  
    }  

    curPath.add(0, end.str);  
    if (!end.prev.isEmpty()) {  
        for (Node prevNode : end.prev) {  
            getPaths(prevNode, map, new ArrayList<String>(curPath), paths);  
        }  
    } else {  
        getPaths(null, map, curPath, paths);  
    }  
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is DP, but not traditional DP question

IT IS DOUBLE DP!

It is very hard for me to even understand the solution, but I have found a great analysis from peking2’s blog.

这题一般人一看就是DP，DP公式也很容易推出，算是一道简单的DP。

dp(i) = min( 1+dp(j+1), if substring(i,j) is palindrome)

从以上的分析时间复杂度为O(n³), 主要是因为检查回文也需要O(n)的时间。因此这题有意思的一点就是如何降低时间复杂度到O(n²)？

其实这题是两个DP混杂在了一起，这也是这道题最有意思的地方。另外一个DP就是跟检查回文有关了，公式如下

dp(i)(j)=true if s(i)==s(j) && dp(i+1)(j-1)

也就是说，你要检查一个回文只需要知道头尾的字符相等，并且中间的字串已经成为了回文即可。O(1)复杂度。

A more detailed analysis is available in this blog.

[Thoughts]
凡是求最优解的，一般都是走DP的路线。这一题也不例外。首先求dp函数，

定义函数
D[i,n] = 区间[i,n]之间最小的cut数，n为字符串长度

 a   b   a   b   b   b   a   b   b   a   b   a
                     i                                  n
如果现在求[i,n]之间的最优解？应该是多少？简单看一看，至少有下面一个解


 a   b   a   b   b   b   a   b   b   a   b   a
                     i                   j  j+1    n

此时  D[i,n] = min(D[i, j] + D[j+1,n])  i<=j <n。这是个二维的函数，实际写代码时维护比较麻烦。所以要转换成一维DP。如果每次，从i往右扫描，每找到一个回文就算一次DP的话，就可以转换为
D[i] = 区间[i,n]之间最小的cut数，n为字符串长度， 则,

D[i] = min(1+D[j+1] )    i<=j <n

有个转移函数之后，一个问题出现了，就是如何判断[i,j]是否是回文？每次都从i到j比较一遍？太浪费了，这里也是一个DP问题。
定义函数
P[i][j] = true if [i,j]为回文

那么
P[i][j] = str[i] == str[j] && P[i+1][j-1];

Solution

The coding is not easy, especially when 2 DP are written in 1 for-loop.

I wrote many times until I finally achieved the nice and concise solution that you see below.

Code

Doing everything in 1 loop, not an intuitive code.

public int minCut(String s) {
    int len = s.length();
    if (len <= 1) return 0;
    boolean[][] pl = new boolean[len][len];
    int[] dp = new int[len];
    for (int i = len-1; i >= 0; i --) {
        dp[i] = Integer.MAX_VALUE;
        for (int j = i; j < len; j ++) {
            // first set pl[][], then update dp[i]
            if (j - i <= 1) pl[i][j] = s.charAt(i) == s.charAt(j);
            else pl[i][j] = s.charAt(i) == s.charAt(j) & pl[i+1][j-1];
            if (pl[i][j]) {
                if (j == len-1) dp[i] = 0;
                else 
                    dp[i] = Math.min(dp[i], dp[j+1] + 1);
            }
        }
    }
    return dp[0];
}

Updated on July 18th, 2014, written by me.

boolean[][] map = null;

public int minCut(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    map = getMap(s);
    int len = s.length();
    int[] dp = new int[len + 1];
    dp[0] = -1;
    for (int i = 0; i < len; i++) {
        dp[i+1] = Integer.MAX_VALUE;
        for (int j = 0; j <= i; j++) {
            if (map[j][i]) {
                dp[i+1] = Math.min(dp[i+1], dp[j] + 1);
            }
        }
    }
    return dp[len];
}

private boolean[][] getMap(String s) {
    int len = s.length();
    boolean[][] map = new boolean[len][len];
    for (int i = len - 1; i >= 0; i--) {
        for (int j = 0; j < len; j++) {
            if (i > j) {
                continue;
            } else if (i == j) {
                map[i][j] = true;
            } else {
                if (i + 1 == j) {
                    map[i][j] = s.charAt(i) == s.charAt(j);
                } else {
                    map[i][j] = s.charAt(i) == s.charAt(j) && map[i+1][j-1];
                }
            }
        }
    }
    return map;
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question is a little tricky, but not difficult. First important thing is to konw what is insertion sort. It is always keeping a sorted list, and then get next unsorted element and insert into correct position of the sorted list.

Solution

Almost all solutions on internet is same, so I will just explain my code. My code can be optimized a little bit by studying this blog, but I guess it’s just refactoring 1 or 2 variables and execution time would not be affected.

My solution is dividing the list into 2 parts: sorted part and unsorted part. I keep getting next node from unsorted and insert into sorted.

My code

Recursion:

public ListNode insertionSortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode sorted = new ListNode(Integer.MIN_VALUE);
    sorted.next = head;
    ListNode unsort = head.next;
    head.next = null;
    // the sorted and unsort both are not null at this point
    while (unsort != null) {
        ListNode pos = sorted;
        ListNode cur = unsort;
        unsort = unsort.next;
        while (pos.next != null && pos.val < cur.val 
            && pos.next.val < cur.val) pos = pos.next;
        // now insert (cur) to (pos.next)
        cur.next = pos.next;
        pos.next = cur;
    }
    return sorted.next;
}

Updated on June 17th, rewrote the code with dummy head. This is different solution, with better readability.

public ListNode insertionSortList(ListNode head) {
    if (head == null) {
        return null;
    }
    ListNode dummy = new ListNode(0);
    ListNode cur = head;
    while (cur != null) {
        // insert cur into correct pos
        ListNode pos = dummy;
        while (pos.next != null && pos.next.val < cur.val) {
            pos = pos.next;
        }
        ListNode temp = cur.next;
        cur.next = pos.next;
        pos.next = cur;
        cur = temp;
    }
    return dummy.next;
}

Question

link

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a difficult coding question, although the idea is simple.

Solution

Two solution: BFS (recommended) and DFS. This is a good analysis article.

Let’s analyze this further by using the below example:

A simple graph

Assume that the starting point of the graph is A. First, you make a copy of node A (A2), and found that A has only one neighbor B. You make a copy of B (B2) and connects A2->B2 by pushing B2 as A2′s neighbor. Next, you find that B has A as neighbor, which you have already made a copy of. Here, we have to be careful not to make a copy of A again, but to connect B2->A2 by pushing A2 as B2′s neighbor. But, how do we know if a node has already been copied?

Basic idea is to use HashMap to store the already-copied nodes.

My first attempt is DFS by making use of a ‘visited’ Set to mark which node I have copied and which is not. This is a nice idea and it solved the problem neatly.

But after reading this article, I realize that ‘visited’ is not needed for BFS solution!

The trick is, whenever I do a ‘HashMap.put(curNode, newNode)’, I push ‘curNode’ to queue. This very well replaces the functionality of the ‘visited’ set. It also guarantees that when I pop a new element from the queue, I CAN ALWAYS FIND ITS CORRESPONDING COPY from the HashMap - always there.

Code

First, my DFS code

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) return null;
    UndirectedGraphNode newNode = new UndirectedGraphNode(node.label);
    HashMap<Integer, UndirectedGraphNode> map = 
        new HashMap<Integer, UndirectedGraphNode>();
    map.put(node.label, newNode);
    copy(node, newNode, map, new HashSet<Integer>());
    return newNode;
}

private void copy(UndirectedGraphNode orin, UndirectedGraphNode cp,
        HashMap<Integer, UndirectedGraphNode> map,
        HashSet<Integer> visited) {
    if (visited.contains(orin.label))
        return;
    else
        visited.add(orin.label);
    for (UndirectedGraphNode n : orin.neighbors) {
        if (map.containsKey(n.label)) {
            cp.neighbors.add(map.get(n.label));
        } else {
            UndirectedGraphNode newNode = new UndirectedGraphNode(n.label);
            map.put(n.label, newNode);
            cp.neighbors.add(map.get(n.label));
        }
    }
    // do DFS recursively
    for (int i = 0; i < orin.neighbors.size(); i++) {
        copy(orin.neighbors.get(i), cp.neighbors.get(i), map, visited);
    }
}

Second, my BFS code without using ‘visited’ HashSet

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
    if (node == null) return null;
    HashMap<UndirectedGraphNode, UndirectedGraphNode> map 
            = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
    map.put(node, new UndirectedGraphNode(node.label));
    LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
    queue.add(node);
    // queue is guaranteed to always have non-traversed nodes
    while ( !queue.isEmpty() ) {
        UndirectedGraphNode orin = queue.remove();
        UndirectedGraphNode cp = map.get(orin);
        for (UndirectedGraphNode n : orin.neighbors) {
            if ( !map.containsKey(n) ) {
                map.put(n, new UndirectedGraphNode(n.label));
                queue.add(n);
            }
            UndirectedGraphNode newNode = map.get(n);
            cp.neighbors.add(newNode);
        }
    }
    return map.get(node);
}

Question

link

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an extremely difficult question.

Solution

1. This question is find shortest path, so we shall choose BFS over DFS.

2. Since finding an element in HashSet is O(1) time, we can generate all the possible strings of distance = 1 and check if they are in the dictionary. In this way, we reduce time complexity from O(m x n) to O(m x 26).

3. If a word is found from the dictionary, remove it.

For the 3rd point, we remove the word from dict. It might be hard to understand. This blog explains it clear enough.

另外一个需要注意的地方就是，如果我们曾经遍历过某个元素，我会将其从字典中删除，以防以后再次遍历到这个元素。这里有几种情况：

1.以后再也遍历不到这个元素，那么我们删除它当然没有任何问题。

2.我们以后会遍历到该元素，又分为两种情况：

(1)在本层我们就能遍历到该元素。也就是说，我们到达这个元素有两条路径，而且它们都是最短路径。

对于本题来说，是没有什么影响的，因为到dog距离都是3，到dig距离都是4。但是后面我们做word ladder 2的时候，如果没有考虑这个情况，将是非常致命的，因为题目要求输出最短路径的所有情况

(2)在更下层我们才能够遍历到该元素。比如hot->dot->dog->dig和hot->hat->dat->dag->dog->dig，如果第一次我们找到了dog并且将其删除，那么第二次我们实际上是找不到这个元素的。这样对于本题来说，没有任何影响。对于word ladder 2来说，因为也是要输出最短路径，所以也不会有任何影响。

Code

BFS solution

This is similar to the code posted in this article.

public int ladderLength(String start, String end, HashSet<String> dict) {
    if (start.equals(end)) return 1;
    LinkedList<String> words = new LinkedList<String>();
    LinkedList<Integer> nums = new LinkedList<Integer>();
    words.add(start);
    nums.add(1);
    while (!words.isEmpty()) {
        String word = words.remove();
        int num = nums.remove();
        // otherwise, change each char in word, and find it from dict
        char[] charArr = word.toCharArray();
        for (int i = 0; i < charArr.length; i++) {
            char originChar = charArr[i];
            for (char j = 'a'; j <= 'z'; j++) {
                charArr[i] = j;
                String newWord = new String(charArr);
                if (newWord.equals(end))
                    return num + 1;
                if (dict.contains(newWord)) {
                    dict.remove(newWord);
                    words.add(newWord);
                    nums.add(num + 1);
                }
            }
            charArr[i] = originChar;
        }
    }
    return 0;
}

Question

link

X X X X
X O O X
X X O X
X O X X

X X X X
X X X X
X X X X
X O X X

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This question can be solved by DFS or BFS search.

The idea is simple. For each edge nodes, if it is an ‘O’, search for all connected ‘O’s and mark it. My first attemps used another array to store result. It works, but it’s actually bad, because space usage is huge. We can actually mark the connected nodes using some special character, for example in my case, 'R’. Then the solution can work in-place.

So this is the standard solution.

Solution

However, there is one big problem with my DFS solution.

For super-large test cases, it gets ‘java.lang.StackOverflowError’ exception. It’s very werid to me, until I read this blog.

If you use DFS Recursive, you will get Runtime Error. But if you implement DFS by stack, just like doing BFS by Queue, your code will get accepted.

Recursive dfs would take too much resource (too many calls which require space to store the calling state) than bfs for long long case. Considering one of test case with 200x200 matrix, in worst case the longest path (number of calls) might take 200x200 = 40,000 long. While with bfs, the maximal calls are about less than 400.

One more thing, so DFS with stack, or BFS with queue, which one would consume less space? I think BFS. The difference is DFS space usage is max depth, while BFS is the max width. However in this question, each node have 4 adjacent nodes, so the DFS space usage would be increased to 3 x (max depth). More details on this topic, please refer to DFS, BFS and space efficiency.

If any reader have an idea on this, please comment!

Code

bfs code realized with a queue

public void solve(char[][] board) {
    if (board.length == 0) return;
    int m = board.length, n = board[0].length;
    for (int i = 0; i < m; i ++) {
        dfs(board, i, 0);
        dfs(board, i, n-1);
    }
    for (int j = 0; j < n; j ++) {
        dfs(board, 0, j);
        dfs(board, m-1, j);
    }
    for (int i = 0; i < m; i ++) 
        for (int j = 0; j < n; j ++) 
            if (board[i][j] == 'R') 
                board[i][j] = 'O';
            else if (board[i][j] == 'O') 
                board[i][j] = 'X';
}

private void dfs(char[][] board, int x, int y) {
    int m = board.length, n = board[0].length;
    Queue<Integer> aa = new LinkedList<Integer>();
    Queue<Integer> bb = new LinkedList<Integer>();
    aa.add(x);
    bb.add(y);
    while (!aa.isEmpty()) {
        int a = aa.remove();
        int b = bb.remove();
        if (a < 0 || a >= m || b < 0 || b >= n) 
            continue;
        if (board[a][b] == 'X' || board[a][b] == 'R') 
            continue;
        board[a][b] = 'R';

        aa.add(a - 1);
        bb.add(b);
        aa.add(a + 1);
        bb.add(b);
        aa.add(a);
        bb.add(b - 1);
        aa.add(a);
        bb.add(b + 1);
    }
}

Question

link

    1
   / \
  2   3

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is DFS standard question.

Solution

I posted 2 pieces of my code, and 1 best code (from this blog).

Code

First, my solution using List.

int sum = 0;

public int sumNumbers(TreeNode root) {
    dfs(root, new LinkedList<Integer>());
    return sum;
}

private void dfs(TreeNode node, LinkedList<Integer> list) {
    if (node == null) return;
    if (node.left == null && node.right == null) {
        int num = 0;
        for (int i = 0; i < list.size(); i ++) 
            num = num * 10 + list.get(i);
        sum += num * 10 + node.val;
        return;
    }
    // if node is not null, not a leaf
    list.add(node.val);
    dfs(node.left, list);
    dfs(node.right, list);
    list.remove(list.size() - 1);
}

Second, previous code refactored, without using list, because it’s not necessary to know the previous path.

int sum = 0;
public int sumNumbers(TreeNode root) {
    dfs(root, 0);
    return sum;
}

private void dfs(TreeNode node, int preVal) {
    if (node == null) return;
    int curVal = preVal * 10 + node.val;
    if (node.left == null && node.right == null) {
        int num = 0;
        sum += curVal;
        return;
    }
    // if node is not null, not a leaf
    dfs(node.left, curVal);
    dfs(node.right, curVal);
}

Third, best solution

public int sumNumbers(TreeNode root) {
    return dfs(root,0);
}

int dfs(TreeNode root, int sum){
    if(root==null) return 0;
    sum=sum*10+root.val;
    if(root.left==null && root.right==null) return sum;
    return dfs(root.left,sum) + dfs(root.right,sum);
}