Leetcode Weekly Contest 117 Q1 and Q2 My Solution

TreeNode.java

import java.util.Stack;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int x) {
        val = x;
    }

    private int getCloseIndex(int begin, String s) {
        Stack<Character> stack = new Stack<>();
        stack.push('(');
        int endIndex = -1;
        for (int i = begin + 1; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push('(');
            } else if (s.charAt(i) == ')') {
                stack.pop();
                if (stack.empty()) {
                    endIndex = i;
                    break;
                }
            }
        }

        if (endIndex == -1) {
            throw new IllegalStateException("Cannot find closing ')' corresponding to '(' at " + begin);
        }
        return endIndex;
    }

    public TreeNode(String s) {
        int index = s.indexOf('(');
        if (index < 0) {
            this.val = Integer.parseInt(s.trim());
        } else {
            this.val = Integer.parseInt(s.substring(0, index).trim());

            int endIndex = this.getCloseIndex(index, s);
            this.left = endIndex - index == 1 ? null : new TreeNode(s.substring(index + 1, endIndex));

            // Allow whitespaces before/after '(' and ')'
            for (int i = endIndex + 1; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    index = i;
                    break;
                }
            }
            endIndex = this.getCloseIndex(index, s);
            this.right = endIndex - index == 1 ? null : new TreeNode(s.substring(index + 1, endIndex));
        }
    }

    @Override
    public String toString() {
        if (left == null && right == null) return String.valueOf(val);
        else return val + String.format("(%s)(%s)",
            left == null ? "" : left.toString(),
            right == null ? "" : right.toString());
    }
}

WeeklyContest117.java

import java.util.ArrayList;
import java.util.List;

import static org.testng.Assert.*;

public class Weekly117 {
    private boolean isUnivalTree(TreeNode root) {
        if (root == null) return true;
        if (root.left != null && root.val != root.left.val) return false;
        if (root.right != null && root.val != root.right.val) return false;
        return isUnivalTree(root.left) && isUnivalTree(root.right);
    }

    @Test
    public void test_isUnivalTree() {
        assertTrue(isUnivalTree(new TreeNode("1(1(1)(1))(1()(1))")));
        assertFalse(isUnivalTree(new TreeNode("2(2(5)(2))(2)")));
    }

    private int[] __numsSameConsecDiff(int n, int k) {
        List<String> paths = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            if (i == 0 && n > 1) continue;

            TreeNode node = new TreeNode(i);
            this._processNode(node, k, 1, n);

            StringBuilder sb = new StringBuilder();
            this.traverse(node, sb, paths);
        }
        paths.removeIf(s -> s.length() != n);
        return paths.stream().mapToInt(Integer::parseInt).toArray();
    }

    @Test
    public void test___numsSameConsecDiff() {
        assertEquals(__numsSameConsecDiff(2, 1), new int[]{10, 12, 21, 23, 32, 34, 43, 45,
            54, 56, 65, 67, 76, 78, 87, 89, 98});
        assertEquals(__numsSameConsecDiff(3, 7), new int[]{181, 292, 707, 818, 929});
        assertEquals(__numsSameConsecDiff(2, 0), new int[]{11, 22, 33, 44, 55, 66, 77, 88, 99});
        assertEquals(__numsSameConsecDiff(1, 0), new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
    }

    private void traverse(TreeNode prev, StringBuilder sb, List<String> paths) {
        sb.append(prev.val);
        // early exit using sb.length() == maxDepth, but prefer to list all possible paths
        if (prev.left == null && prev.right == null) {
            paths.add(sb.toString());
            return;
        }

        if (prev.left != null) {
            traverse(prev.left, sb, paths);
            sb.setLength(sb.length() - 1);
        }

        if (prev.right != null) {
            traverse(prev.right, sb, paths);
            sb.setLength(sb.length() - 1);
        }
    }

    private void _processNode(TreeNode root, int k, int currDep, int maxDep) {
        if (root == null || currDep >= maxDep) return;

        int left = root.val - k;
        int right = root.val + k;
        if (left >= 0 && left < 10) root.left = new TreeNode(left);
        // Check right != left to avoid duplicates when k == 0
        if (right >= 0 && right < 10 && right != left) root.right = new TreeNode(right);
        if (currDep + 1 == maxDep) return;

        _processNode(root.left, k, currDep + 1, maxDep);
        _processNode(root.right, k, currDep + 1, maxDep);
    }

    private int[] numsSameConsecDiff(int n, int k) {
        List<Integer> results = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            if (i == 0 && n > 1) continue;
            processNode(new TreeNode(i), k, 1, n, results);
        }
        return results.stream().mapToInt(j -> j).toArray();
    }

    private void processNode(TreeNode node, int k, int currDepth, int maxDepth, final List<Integer> results) {
        if (node == null) return;

        if (currDepth == maxDepth) {
            results.add(node.val);
        } else {
            int previous = node.val % 10;
            int left = previous - k;
            int right = previous + k;
            // We can set leaf node value in append mode directly, or we can use StringBuilder to concatenate them
            if (left >= 0 && left < 10) node.left = new TreeNode(node.val * 10 + left);
            if (right >= 0 && right < 10 && right != left) node.right = new TreeNode(node.val * 10 + right);
            if (currDepth + 1 == maxDepth) {
                if (node.left != null) results.add(node.left.val);
                if (node.right != null) results.add(node.right.val);
            } else {
                processNode(node.left, k, currDepth + 1, maxDepth, results);
                processNode(node.right, k, currDepth + 1, maxDepth, results);
            }
        }
    }

    @Test
    public void test_numsSameConsecDiff() {
        assertEquals(numsSameConsecDiff(2, 0), new int[]{11, 22, 33, 44, 55, 66, 77, 88, 99});
        assertEquals(numsSameConsecDiff(1, 0), new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
        assertEquals(numsSameConsecDiff(2, 1), new int[]{10, 12, 21, 23, 32, 34, 43, 45,
            54, 56, 65, 67, 76, 78, 87, 89, 98});
        assertEquals(numsSameConsecDiff(3, 7), new int[]{181, 292, 707, 818, 929});
    }

    @Test
    public void test__numsSameConsecDiff() {
        assertEquals(_numsSameConsecDiff(2, 0), new int[]{11, 22, 33, 44, 55, 66, 77, 88, 99});
        assertEquals(_numsSameConsecDiff(1, 0), new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9});
        assertEquals(_numsSameConsecDiff(2, 1), new int[]{10, 12, 21, 23, 32, 34, 43, 45,
            54, 56, 65, 67, 76, 78, 87, 89, 98});
        assertEquals(_numsSameConsecDiff(3, 7), new int[]{181, 292, 707, 818, 929});
    }

    private int[] _numsSameConsecDiff(int n, int k) {
        List<String> list = new ArrayList<>();
        for (int i = 0; i <= 9; i++) {
            if (n > 1 && i == 0) {
                continue;
            }
            StringBuilder sb = new StringBuilder();
            sb.append(i);
            dfs(n, k, sb, i, list);
        }
        System.out.println(list);
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }

    private void dfs(int n, int k, StringBuilder sb, int last, List<String> list) {
        if (sb.length() == n) {
            list.add(sb.toString());
            return;
        }
        if (last - k >= 0) {
            sb.append(last - k);
            dfs(n, k, sb, last - k, list);
            sb.setLength(sb.length() - 1);
        }
        if (k > 0 && last + k <= 9) {
            sb.append(last + k);
            dfs(n, k, sb, last + k, list);
            sb.setLength(sb.length() - 1);
        }
    }

}