Valid Parenthesis String
Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:
Example 1:
Input: "()"
Output: True
Example 2:
Input: "(*)"
Output: True
Example 3:
Input: "(*))"
Output: True
Note: The string size will be in the range [1, 100].
GIT URL: Java Solution of Leet Code's Product of Valid Parenthesis String problem
Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules:
- Any left parenthesis '(' must have a corresponding right parenthesis ')'.
- Any right parenthesis ')' must have a corresponding left parenthesis '('.
- Left parenthesis '(' must go before the corresponding right parenthesis ')'.
- '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
- An empty string is also valid.
Example 1:
Input: "()"
Output: True
Example 2:
Input: "(*)"
Output: True
Example 3:
Input: "(*))"
Output: True
Note: The string size will be in the range [1, 100].
GIT URL: Java Solution of Leet Code's Product of Valid Parenthesis String problem
Java Solution
Construct Binary Search Tree from Preorder Traversal
Return the root node of a binary search tree that matches the given preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
Example 1:
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Note
1 <= preorder.length <= 100
The values of preorder are distinct.
Algorithm
1). We will write a recursive function constructTree(), which will create a Binary tree from preorder. This function will take preorder, preIndex, min and max.
2). We will first construct the root node of BST which would be the first key in the preorder sequence. But before this we will check if key is greater than min (which is Integer.MIN_VALUE for root node) and less than max(which is Integer.MAX_VALUE for the root node).
3). Call the recursive function for the left sub-tree with keys in the preorder sequence that appears before the i'th index (excluding first index).
4). Call the recursive function for the right sub-tree with keys in the preorder sequence that appears after the i'th index (including i'th index)
Return the root node of a binary search tree that matches the given preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
Example 1:
Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]
Note
1 <= preorder.length <= 100
The values of preorder are distinct.
Algorithm
1). We will write a recursive function constructTree(), which will create a Binary tree from preorder. This function will take preorder, preIndex, min and max.
2). We will first construct the root node of BST which would be the first key in the preorder sequence. But before this we will check if key is greater than min (which is Integer.MIN_VALUE for root node) and less than max(which is Integer.MAX_VALUE for the root node).
3). Call the recursive function for the left sub-tree with keys in the preorder sequence that appears before the i'th index (excluding first index).
4). Call the recursive function for the right sub-tree with keys in the preorder sequence that appears after the i'th index (including i'th index)
GIT URL: Java Solution of Leet Code's Product of Construct Binary Search Tree From Preorder problem
-K Himaanshu Shuklaa..
Java Solution
No comments:
Post a Comment