Skip to content

Instantly share code, notes, and snippets.

@ny83427 ny83427/TreeNode.java
Last active Dec 31, 2018

Embed
What would you like to do?
Leetcode Weekly Contest 117 Q1 and Q2 My Solution
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());
}
}
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);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.