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
        nodes.add(node.val);

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

        // 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));
        }
    }
}
Advertisements

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],
  [3]
]
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<>();
            levelList.add(root.val);
            result.add(0, levelList);
        } else {
            result.get(result.size() - level).add(root.val);
        }

        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.LinkedList;
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();
                levelList.add(curr.val);

                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
            }
            result.add(0, levelList);
        }
        return result;
    }

}