# 113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and `sum = 22`,

```      5
/ \
4   8
/   / \
11  13  4
/  \    / \
7    2  5   1
```

Return:

```[
[5,4,11,2],
[5,8,4,5]
]```

Code

```package second100;

import general.TreeNode;

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

public class Problem113 {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new ArrayList<>();

if (root == null) {
return result;
}

pathSum(root, result, 0, sum, new ArrayList<>());
return result;
}

private void pathSum(TreeNode node, List<List<Integer>> result, int currentSum, int sum, List<Integer> nodes) {
// Base case
// Leaf node

if (node.left == null && node.right == null) {
if (currentSum + node.val == sum) {
}
}

// Recursion
if (node.left != null) {
pathSum(node.left, result, currentSum + node.val, sum, new ArrayList<>(nodes));
}

if (node.right != null) {
pathSum(node.right, result, currentSum + node.val, sum, new ArrayList<>(nodes));
}
}
}```

# 112. Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

Note: A leaf is a node with no children.

Example:

Given the below binary tree and `sum = 22`,

```      5
/ \
4   8
/   / \
11  13  4
/  \      \
7    2      1
```

return true, as there exist a root-to-leaf path `5->4->11->2` which sum is 22.

Code

```package second100;

import general.TreeNode;

public class Problem112 {

public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}

return hasPathSum(root, 0, sum);
}

private boolean hasPathSum(TreeNode node, int currentSum, int sum) {
// Base case
// leaf nodes
if (node.left == null && node.right == null) {
return currentSum + node.val == sum;
}

// Recursion
boolean result = false;
if (node.left != null) {
result = result || hasPathSum(node.left, currentSum + node.val, sum);
}

if (node.right != null) {
result = result || hasPathSum(node.right, currentSum + node.val, sum);
}
return result;
}

}```

# 111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example:

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

```    3
/ \
9  20
/  \
15   7```

return its minimum depth = 2.

Code

```package second100;

import general.TreeNode;

public class Problem111 {

public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}

return minDepthHelper(root);
}

private int minDepthHelper(TreeNode root) {
if (root == null) {
return 0;
}

int leftDepth = minDepthHelper(root.left);
int rightDepth = minDepthHelper(root.right);

if (leftDepth == 0 && rightDepth == 0) {
return 1;
}

if (leftDepth == 0) {
return rightDepth + 1;
}

if (rightDepth == 0) {
return leftDepth + 1;
}

return Math.min(leftDepth, rightDepth) + 1;
}

}```

# 110. Balanced Binary Tree

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Given the following tree `[3,9,20,null,null,15,7]`:

```    3
/ \
9  20
/  \
15   7```

Return true.

Example 2:

Given the following tree `[1,2,2,3,3,null,null,4,4]`:

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

Return false.

Code
```package second100;

import general.TreeNode;

public class Problem110 {

public static void main(String[] args) {
//[3,9,20,null,null,15,7]
TreeNode node3 = new TreeNode(3);
TreeNode node9 = new TreeNode(9);
TreeNode node20 = new TreeNode(20);
TreeNode node15 = new TreeNode(15);
TreeNode node7 = new TreeNode(7);

node3.left = node9;
node3.right = node20;
node20.left = node15;
node20.right = node7;

System.out.println(new Problem110().isBalanced(node3));
}

public boolean isBalanced(TreeNode root) {
// Base case
if (root == null) {
return true;
}

int leftDepth = findDepth(root.left);
int rightDepth = findDepth(root.right);
boolean bool = Math.abs(leftDepth - rightDepth) <= 1;
return bool && isBalanced(root.left) && isBalanced(root.right);
}

private int findDepth(TreeNode node) {
// Base case
if (node == null) {
return 0;
}

int leftDepth = findDepth(node.left);
int rightDepth = findDepth(node.right);
return Math.max(leftDepth, rightDepth) + 1;
}
}```

# 108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

```Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

0
/ \
-3   9
/   /
-10  5
```
Code
```package second100;

import general.TreeNode;

public class Problem108 {

public static void main(String[] args) {
int[] nums = new int[] {-10, -3, 0, 5, 9};

Problem108 app = new Problem108();
app.sortedArrayToBST(nums);
}

public TreeNode sortedArrayToBST(int[] nums) {
if (nums == null) {
return null;
}
return sortedArrayToBST(nums, 0, nums.length - 1);
}

private TreeNode sortedArrayToBST(int[] nums, int start, int end) {
// Base case
if (start > end) {
return null;
}

if (start == end) {
return new TreeNode(nums[start]);
}

// Recursive case
int centerIndex = findCenterIndex(start, end);
TreeNode node = new TreeNode(nums[centerIndex]);
node.setLeft(sortedArrayToBST(nums, start, centerIndex - 1));
node.setRight(sortedArrayToBST(nums, centerIndex + 1, end));
return node;
}

private int findCenterIndex(int start, int end) {
return (int) ((start) + Math.ceil((end - start) / 2.0));
}
}```

# 107. Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree `[3,9,20,null,null,15,7]`,

```    3
/ \
9  20
/  \
15   7
```

return its bottom-up level order traversal as:

```[
[15,7],
[9,20],

]
```
Analysis
Option 1: Pre preoder traversal and keep storing the results
Option 2: Do level order traversal and then reverse
Code
Option1 :
```package second100;

import general.TreeNode;

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

public class Problem107 {

public static void main(String[] args) {
TreeNode node3 = new TreeNode(3);
TreeNode node9 = new TreeNode(9);
TreeNode node20 = new TreeNode(20);
TreeNode node15 = new TreeNode(15);
TreeNode node7 = new TreeNode(7);

node3.setLeft(node9);
node3.setRight(node20);
node20.setLeft(node15);
node20.setRight(node7);

Problem107 app = new Problem107();
System.out.println(app.levelOrderBottom(node3));
}

public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
levelOrderBottom(root, result, 1);
return result;
}

private void levelOrderBottom(TreeNode root, List<List<Integer>> result, int level) {
if (root == null)
return;

if (result.size() < level) {
List<Integer> levelList = new ArrayList<>();
} else {
}

levelOrderBottom(root.left, result, level + 1);
levelOrderBottom(root.right, result, level + 1);
}

}```

Option2:

```package second100;

import general.TreeNode;

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

public class Problem107 {

public static void main(String[] args) {
TreeNode node3 = new TreeNode(3);
TreeNode node9 = new TreeNode(9);
TreeNode node20 = new TreeNode(20);
TreeNode node15 = new TreeNode(15);
TreeNode node7 = new TreeNode(7);

node3.setLeft(node9);
node3.setRight(node20);
node20.setLeft(node15);
node20.setRight(node7);

Problem107 app = new Problem107();
System.out.println(app.levelOrderBottom1(node3));
System.out.println(app.levelOrderBottom2(node3));
}

private List<List<Integer>> levelOrderBottom2(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null)
return result;

Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);

while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> levelList = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode curr = queue.poll();

if (curr.left != null) {
queue.offer(curr.left);
}
if (curr.right != null) {
queue.offer(curr.right);
}
}