[LeetCode Java Solution] – String/DFS – Generate Parentheses

Problem:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

Method:

How to understand DFS? Determine how many branches we have? For each branch, we call recursive helper method. So overall, we will find out all the solutions for one branch and then go to another branch and do the same thing.

Remember: in each level, we have to make sure the variables are not changed, since we still need to go to the next branch.

Code:

public class Solution {
    ArrayList<String> res = new ArrayList<String>();
    
    public ArrayList<String> generateParenthesis(int n) {
        if (n == 0) return res;
        helper(n, n, "");
        return res;
    }
    
    public void helper(int left, int right, String item){
        if (left > right) return;
        if (left == 0 && right == 0){
            res.add(item);
        }
        if (left > 0){
            helper(left-1, right, item + "(");
            // remember that one each level, you can't change the variables.
        }
        if (right > 0){
            helper(left, right-1, item + ")");
        }
    }
}

[LeetCode Java Solution] – DFS – Sum Root to Leaf Numbers

Problem:

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

Method:

1. Use recursive method to implement DFS. Every time we input a temp sum and current node, and return the new updated temp sum.

2. Use a integer res to store the final summation. And this integer variable has to be outside of the two method.

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 // make an external variable res to store the value. 
public class Solution {
    int res = 0;  // this has to be outside of the two methods.
    public int sumNumbers(TreeNode root) {
        if (root == null) return 0;
        sum(root, 0);
        return res;
    }
    
    public void sum(TreeNode root, int tmpsum){
        if (root.left == null && root.right == null){
            res += tmpsum*10 + root.val;
        }
        if (root.left != null){
            sum(root.left, tmpsum*10 + root.val);
        }
        if (root.right != null){
            sum(root.right, tmpsum*10 + root.val);
        }
    }
}

[LeetCode]-dfs – Validate Binary Search Tree

Problem:

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.

confused what "{1,#,2,3}" means?

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.Here’s an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

Method 0: 

Brute force. O(n^2).

Code for method 0:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        else return isLess(root.left, root.val)&& isGreat(root.right, root.val)
        && isValidBST(root.left)&& isValidBST(root.right);
    }
    
    public boolean isLess(TreeNode root, int i){
        if (root == null) return true;
        if (root.val < i){
            return isLess(root.left, i) && isLess(root.right, i);
        }else return false;
    }
    
    public boolean isGreat(TreeNode root, int i){
        if (root == null) return true;
        if (root.val > i){
            return isGreat(root.left, i) && isGreat(root.right, i);
        }else return false;
    } 
}

Method 1:

• O(n).
• Possible mistake: Can not use Recursive. Remember, for a BST, everything on the right can not be larger than the root, not only for root.right. Same for the left.
• First, we could simply view it as a in-order traversal problem. However, we do need an external space to record the current min for the previous all steps.

Code for method 1:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */


public class Solution {
    public boolean isValidBST(TreeNode root) {
        ArrayList<Integer> pre = new ArrayList<Integer>();// to store the max value 
        pre.add(null);
        return helper(root,pre);
    }
    public boolean helper (TreeNode root, ArrayList<Integer> pre){
        if (root == null) return true;
        boolean left = helper(root.left, pre);
        if (left == false) return false;
        if (pre.get(0) !=null && root.val <= pre.get(0)) return false;
        pre.set(0,root.val);
        return helper(root.right, pre);
    }
}

 Method 2:

• Remember an upper bound, and an lower bound along the binary search tree.
• If go to the left child, update the upper bound. If go to the right child, update the lower bound.
• Detail: have to be careful about exceeding Integer range. Have to use type long to pass the auto-checker.
• Detail of concept: Pre-order, In-order, and Post-order traversals all belong to depth-first traversal.
• O(n)

Code for method 2:

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