LeetCode 98. Validate Binary Search Tree

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

Input:
    2
   / \
  1   3
Output: true

Example 2:

    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public boolean isValidBST(TreeNode root) {
	// corner cases
	if (root == null) {
	return true;
	}
	return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
	}
	public boolean isValidBST(TreeNode root, long min, long max) {
	// corner cases
	if (root == null) {
	return true;
	}
	if (root.val <= min || root.val >= max) {
	return false;
	}
	return isValidBST(root.left, min, Math.min(max, root.val)) && isValidBST(root.right, Math.max(min, root.val), max);
	}
	}

view raw 98. Validate Binary Search Tree.java hosted with ❤ by GitHub

LeetCode 200. Number of Islands.java

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

	class Solution {
	public int numIslands(char[][] grid) {
	// corner cases
	if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
	return 0;
	}
	// main logic - 2 for loops and using every non visited land as entry point to call dfs
	int counter = 0;
	m = grid.length;
	n = grid[0].length;
	visited = new boolean[m][n];
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if ( !visited[i][j] && (grid[i][j] == '1')) {
	dfs(grid, i, j);
	counter++;
	}
	}
	}
	return counter;
	}
	private int m = 0;
	private int n = 0;
	private boolean[][] visited = null;
	private int[] dx = new int[]{0, 0, 1, -1};
	private int[] dy = new int[]{1, -1, 0, 0,};
	private void dfs(char[][] grid, int i , int j) {
	// corner cases
	if (visited[i][j] || grid[i][j] == '0') {
	return;
	}
	visited[i][j] = true;
	for (int t = 0; t < 4; t++) {
	int x = dx[t] + i;
	int y = dy[t] + j;
	if (isValid(x, y) && !visited[x][y] && (grid[x][y] == '1')) {
	dfs(grid, x, y);
	}
	}
	}
	private boolean isValid(int x, int y) {
	return x >= 0 && x < m && y >= 0 && y < n;
	}
	}

view raw 200. Number of Islands.java hosted with ❤ by GitHub

LeetCode 872. Leaf-Similar Trees.java

Consider all the leaves of a binary tree.  From left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public boolean leafSimilar(TreeNode root1, TreeNode root2) {
	List<Integer> lst1 = inOrder(root1);
	List<Integer> lst2 = inOrder(root2);
	if (lst1 == null && lst2 == null) {
	return true;
	}
	if (lst1 != null && lst2 == null) {
	return false;
	}
	if (lst1 == null && lst2 != null) {
	return false;
	}
	if (lst1.size() != lst2.size()) {
	return false;
	}
	for (int i = 0; i < lst1.size(); i++) {
	if (lst1.get(i) != lst2.get(i)) {
	return false;
	}
	}
	return true;
	}
	private List<Integer> inOrder(TreeNode root) {
	// corner cases
	if (root == null) {
	return new LinkedList<>();
	}
	List<Integer> lst = new LinkedList<>();
	if (root.left == null && root.right == null) {
	lst.add(root.val);
	return lst;
	}
	if (root.left != null) {
	lst.addAll(inOrder(root.left));
	}
	if (root.right != null) {
	lst.addAll(inOrder(root.right));
	}
	return lst;
	}
	}

view raw 872. Leaf-Similar Trees.java hosted with ❤ by GitHub

LeetCode 559. Maximum Depth of N-ary Tree.java

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example, given a 3-ary tree:

We should return its max depth, which is 3.

Note:

1. The depth of the tree is at most 1000.
2. The total number of nodes is at most 5000.

	/*
	// Definition for a Node.
	class Node {
	public int val;
	public List<Node> children;
	public Node() {}
	public Node(int _val,List<Node> _children) {
	val = _val;
	children = _children;
	}
	};
	*/
	class Solution {
	public int maxDepth(Node root) {
	// corner case
	if (root == null) {
	return 0;
	}
	if (root.children == null || root.children.isEmpty()) {
	return 1;
	}
	int max = Integer.MIN_VALUE;
	for (Node node: root.children) {
	max = Math.max(max, maxDepth(node) );
	}
	return max + 1;
	}
	}

view raw 559. Maximum Depth of N-ary Tree.java hosted with ❤ by GitHub

LeetCode 897. Increasing Order Search Tree.java

Given a tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only 1 right child.

Example 1:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
     3
      \
       4
        \
         5
          \
           6
            \
             7
              \
               8
                \
                 9  

Note:

1. The number of nodes in the given tree will be between 1 and 100.
2. Each node will have a unique integer value from 0 to 1000.

	/**
	* Definition for a binary tree node.
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	class Solution {
	public TreeNode increasingBST(TreeNode root) {
	// corner cases
	if (root == null) {
	return null;
	}
	return inorder(root, null);
	}
	private TreeNode inorder(TreeNode root, TreeNode tail) {
	// corner cases
	if (root == null) {
	return tail;
	}
	TreeNode head = inorder(root.left, root);
	root.left = null;
	root.right = inorder(root.right, tail);
	return head;
	}
	}

view raw 897. Increasing Order Search Tree.java hosted with ❤ by GitHub

LeetCode 101. Symmetric Tree.java

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

	class Solution {
	public boolean isSymmetric(TreeNode root) {
	// corner cases
	if (root == null) {
	return true;
	}
	return isSymmetric(root.left, root.right);
	}
	public boolean isSymmetric(TreeNode left, TreeNode right) {
	// corner cases
	if (left == null && right == null) {
	return true;
	}
	if (left == null && right != null) {
	return false;
	}
	if (left != null && right == null) {
	return false;
	}
	return left.val == right.val && isSymmetric(left.left, right.right) && isSymmetric(left.right, right.left);
	}
	}

view raw 101. Symmetric Tree.java hosted with ❤ by GitHub

LeetCode 104. Maximum Depth of Binary Tree

Example:

Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its depth = 3.

	class Solution {
	public int maxDepth(TreeNode root) {
	// corner case
	if (root == null) {
	return 0;
	}
	// call the childrens recursively
	return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
	}
	}

view raw 104. Maximum Depth of Binary Tree.java hosted with ❤ by GitHub

LeetCode 339. Nested List Weight Sum

https://leetcode.com/problems/nested-list-weight-sum/submissions/

Example 1:

Input: [[1,1],2,[1,1]]
Output: 10 
Explanation: Four 1's at depth 2, one 2 at depth 1.

Example 2:

Input: [1,[4,[6]]]
Output: 27 
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3; 1 + 4*2 + 6*3 = 27.

	/**
	* // This is the interface that allows for creating nested lists.
	* // You should not implement it, or speculate about its implementation
	* public interface NestedInteger {
	* // Constructor initializes an empty nested list.
	* public NestedInteger();
	*
	* // Constructor initializes a single integer.
	* public NestedInteger(int value);
	*
	* // @return true if this NestedInteger holds a single integer, rather than a nested list.
	* public boolean isInteger();
	*
	* // @return the single integer that this NestedInteger holds, if it holds a single integer
	* // Return null if this NestedInteger holds a nested list
	* public Integer getInteger();
	*
	* // Set this NestedInteger to hold a single integer.
	* public void setInteger(int value);
	*
	* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
	* public void add(NestedInteger ni);
	*
	* // @return the nested list that this NestedInteger holds, if it holds a nested list
	* // Return null if this NestedInteger holds a single integer
	* public List<NestedInteger> getList();
	* }
	*/
	class Solution {
	public int depthSum(List<NestedInteger> nestedList) {
	// handle corner case inputs
	if (nestedList == null || nestedList.size() == 0) {
	return 0;
	}
	// call DFS to solve this nested list recursivly
	return depthSum(nestedList, 1);
	}
	private int depthSum(List<NestedInteger> lst, int depth) {
	// handle corner case inputs
	if (lst == null || lst.size() == 0) {
	return 0;
	}
	int result = 0;
	for (NestedInteger entry: lst) {
	if (entry.isInteger()) {
	// a number!
	result += entry.getInteger() * depth;
	} else {
	// a nested list!
	result += depthSum(entry.getList(), depth + 1);
	}
	}
	return result;
	}
	}

view raw 339. Nested List Weight Sum.java hosted with ❤ by GitHub

LeetCode Weekly 124 - 995. Minimum Number of K Consecutive Bit Flips

995. Minimum Number of K Consecutive Bit Flips
In an array A containing only 0s and 1s, a K-bit flip consists of choosing a (contiguous) subarray of length K and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0. Return the minimum number of K-bit flips required so that there is no 0 in the array. If it is not possible, return -1.

	public class MinimumNumberOfKConsecutiveBitFlips_995 {
	private final static Logger logger = LoggerFactory.getLogger(MinimumNumberOfKConsecutiveBitFlips_995.class);
	public static void main(String[] args) {
	MinimumNumberOfKConsecutiveBitFlips_995 thisClass = new MinimumNumberOfKConsecutiveBitFlips_995();
	thisClass.testMinimumNumberOfKConsecutiveBitFlips_995();
	}
	private void testMinimumNumberOfKConsecutiveBitFlips_995() {
	logger.info("result {} v.s. {}", "2", minKBitFlips(new int[]{0, 1, 0}, 1));
	logger.info("result {} v.s. {}", "-1", minKBitFlips(new int[]{1, 1, 0}, 2));
	logger.info("result {} v.s. {}", "3", minKBitFlips(new int[]{0, 0, 0, 1, 0, 1, 1, 0}, 3));
	logger.info("result {} v.s. {}", "-1", minKBitFlips(new int[]{1, 0, 1}, 3));
	}
	public int minKBitFlips(int[] A, int K) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return 0;
	}
	// dp logic
	if (K == 1) {
	int count = 0;
	for (int a : A) {
	if (a == 0) {
	count++;
	}
	}
	return count;
	}
	int i = 0;
	int n = A.length;
	int steps = 0;
	while (i < n) {
	if (A[i] == 1) {
	i++;
	continue;
	}
	if (i > n - K) {
	return -1;
	}
	for (int t = 0; t < K; t++) {
	A[i + t] = A[i + t] == 0 ? 1 : 0;
	}
	i++;
	steps++;
	}
	// return the final result
	return steps;
	}
	private static class MyLogger {
	private static final boolean isDebugging = false;
	private static final boolean isInfoing = true;
	private static final String DEBUG = "[DEBUG]";
	private static final String INFO = "[INFO]";
	static void debug(Object message) {
	if (isDebugging) {
	System.out.println(DEBUG + " = " + message);
	}
	}
	static void info(Object message) {
	if (isInfoing) {
	System.out.println(INFO + " = " + message);
	}
	}
	static void debug() {
	if (isDebugging) {
	System.out.println(DEBUG + " = ");
	}
	}
	static void info() {
	if (isInfoing) {
	System.out.println(INFO + " = ");
	}
	}
	}
	}

view raw MinimumNumberOfKConsecutiveBitFlips_995.java hosted with ❤ by GitHub

LeetCode Weekly 124 - 994. Rotting Oranges

994. Rotting Oranges
In a given grid, each cell can have one of three values: the value 0 representing an empty cell; the value 1 representing a fresh orange; the value 2 representing a rotten orange. Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1 instead.

	public class RottingOranges_994 {
	private final static Logger logger = LoggerFactory.getLogger(RottingOranges_994.class);
	public static void main(String[] args) {
	RottingOranges_994 thisClass = new RottingOranges_994();
	thisClass.testRottingOranges_994();
	}
	private void testRottingOranges_994() {
	logger.info("result {} v.s. {}", "4", orangesRotting(new int[][]{
	{2, 1, 1}, {1, 1, 0}, {0, 1, 1}
	}));
	logger.info("result {} v.s. {}", "-1", orangesRotting(new int[][]{
	{2, 1, 1}, {0, 1, 1}, {1, 0, 1}
	}));
	logger.info("result {} v.s. {}", "0", orangesRotting(new int[][]{
	{0, 2}
	}));
	}
	public int orangesRotting(int[][] grid) {
	// filter abnormal cases
	if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
	return 0;
	}
	// searching logic
	int m = grid.length, n = grid[0].length;
	List<Point> list = new ArrayList<>();
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (grid[i][j] == 2) {
	list.add(new Point(i, j));
	}
	}
	}
	int turns = 0;
	boolean isMakingProgress = true;
	while (isMakingProgress) {
	isMakingProgress = false;
	List<Point> tmpList = new ArrayList<>();
	for (Point point : list) {
	for (int t = 0; t < 4; t++) {
	int x = dx[t] + point.x;
	int y = dy[t] + point.y;
	if (x >= 0 && y >= 0 && x < m && y < n) {
	if (grid[x][y] == 1) {
	grid[x][y] = 2;
	tmpList.add(new Point(x, y));
	isMakingProgress = true;
	}
	}
	}
	}
	if (isMakingProgress) {
	list.addAll(tmpList);
	turns++;
	}
	}
	// return the final result
	return hasFresh(grid) ? -1 : turns;
	}
	int[] dx = new int[]{0, 0, 1, -1};
	int[] dy = new int[]{1, -1, 0, 0};
	private boolean hasFresh(int[][] grid) {
	int m = grid.length, n = grid[0].length;
	for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
	if (grid[i][j] == 1) {
	return true;
	}
	}
	}
	return false;
	}
	private class Point {
	int x;
	int y;
	public Point(int x, int y) {
	this.x = x;
	this.y = y;
	}
	}
	private static class MyLogger {
	private static final boolean isDebugging = false;
	private static final boolean isInfoing = true;
	private static final String DEBUG = "[DEBUG]";
	private static final String INFO = "[INFO]";
	static void debug(Object message) {
	if (isDebugging) {
	System.out.println(DEBUG + " = " + message);
	}
	}
	static void info(Object message) {
	if (isInfoing) {
	System.out.println(INFO + " = " + message);
	}
	}
	static void debug() {
	if (isDebugging) {
	System.out.println(DEBUG + " = ");
	}
	}
	static void info() {
	if (isInfoing) {
	System.out.println(INFO + " = ");
	}
	}
	}
	}

view raw RottingOranges_994.java hosted with ❤ by GitHub

LeetCode Weekly 124 - 993. Cousins in Binary Tree

993. Cousins in Binary Tree 
 In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1. Two nodes of a binary tree are cousins if they have the same depth, but have different parents. We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree. Return true if and only if the nodes corresponding to the values x and y are cousins.

	public class CousinsInBinaryTree_993 {
	private final static Logger logger = LoggerFactory.getLogger(CousinsInBinaryTree_993.class);
	public static void main(String[] args) {
	CousinsInBinaryTree_993 thisClass = new CousinsInBinaryTree_993();
	thisClass.testCousinsInBinaryTree_993();
	}
	private void testCousinsInBinaryTree_993() {
	TreeNode root = new TreeNode(1);
	root.left = new TreeNode(2);
	root.left.left = new TreeNode(4);
	root.right = new TreeNode(3);
	logger.info("result {} v.s. {}", "false", isCousins(root, 4, 3));
	root.left.left = null;
	root.left.right = new TreeNode(4);
	root.right.right = new TreeNode(5);
	logger.info("result {} v.s. {}", "true", isCousins(root, 5, 4));
	root.right.right = null;
	logger.info("result {} v.s. {}", "false", isCousins(root, 2, 3));
	}
	TreeNode xParent = null;
	TreeNode yParent = null;
	int xDepth = -1;
	int yDepth = -1;
	public boolean isCousins(TreeNode root, int x, int y) {
	// filter abnormal cases
	if (root == null) {
	return false;
	}
	// dp logic
	xParent = null;
	yParent = null;
	xDepth = -1;
	yDepth = -1;
	isCousinsHelper(root, null, 0, x, y);
	// return the final result
	return (xParent != null && xParent != yParent && xDepth == yDepth);
	}
	private void isCousinsHelper(TreeNode root, TreeNode parent, int depth, int x, int y) {
	if (root == null) {
	return;
	}
	if (xParent == null && root.val == x) {
	xParent = parent;
	xDepth = depth;
	}
	if (yParent == null && root.val == y) {
	yParent = parent;
	yDepth = depth;
	}
	isCousinsHelper(root.left, root, depth + 1, x, y);
	isCousinsHelper(root.right, root, depth + 1, x, y);
	}
	public class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) {
	val = x;
	}
	}
	private static class MyLogger {
	private static final boolean isDebugging = false;
	private static final boolean isInfoing = true;
	private static final String DEBUG = "[DEBUG]";
	private static final String INFO = "[INFO]";
	static void debug(Object message) {
	if (isDebugging) {
	System.out.println(DEBUG + " = " + message);
	}
	}
	static void info(Object message) {
	if (isInfoing) {
	System.out.println(INFO + " = " + message);
	}
	}
	static void debug() {
	if (isDebugging) {
	System.out.println(DEBUG + " = ");
	}
	}
	static void info() {
	if (isInfoing) {
	System.out.println(INFO + " = ");
	}
	}
	}
	}

view raw CousinsInBinaryTree_993.java hosted with ❤ by GitHub