Rocky
BAN USERClass Solution{
public TreeNode LCA(TreeNode root, TreeNode a, TreeNode b){
if(root == null){
return null;
}
if(root == a || root == b){
return root;
}
TreeNode leftSide = LCA(root.left, a, b);
TreeNode rightSide = LCA(root.right, a, b);
if(leftSide!=null && rightSide!=null){
return root;
}
return leftSide==null?rightSide:leftSide;
}
}
Class Solution{
public TreeNode LCA(TreeNode root, TreeNode a, TreeNode b){
if(root == null){
return null;
}
if(root == a || root == b){
return root;
}
TreeNode leftSide = LCA(root.left, a, b);
TreeNode rightSide = LCA(root.right, a, b);
if(leftSide!=null && rightSide!=null){
return root;
}
return leftSide==null?rightSide:leftSide;
}
}
This is the iterative solution using Stack in JAVA
public void flatten(TreeNode root) {
// Start typing your Java solution below
// DO NOT write main() function
if(root == null){
return;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode previous = null;
while(!stack.empty()){
TreeNode current = stack.pop();
if (current.right!=null) {
stack.push(current.right);
}
if (current.left!=null) {
stack.push(current.left);
}
current.left = null;
current.right = null;
if (current == root) {
previous = current;
}
else{
previous.right = current;
previous = current;
}
}
}
Repednaheeks, Android test engineer at Automated Traders Desk
I am Edna, a blogger . As an editor with a strong background in English and Hindi language. I enjoy writing ...
Repamberdjohnson859, Backend Developer at ABC TECH SUPPORT
We are Responsible Environmental Technicians utilizing all of the resources available to develop practical solutions to corporate issues. Currently doing ...
RepAveryPerez, abc at 8x8
I am a self-driven and motivated librarian skilled at providing excellent public service to students and staff, managing the library ...
RepSidneyWarren, Development Support Engineer at Abs india pvt. ltd.
Sidney , Materials Planner adept at analyzing the usage of production materials, managing inventories, coordinating new personnel vashikaran specialist contact number ...
RepEzraClark, Analyst at 8x8
I am an experienced multimedia journalist with a background in investigative reporting. I work well with photographers and videographers when ...
This is my solution, I think space complexity should be O(n), Since I use backtrack, time complexity is not very well.
- Rocky February 17, 2013My output sequence is different:fab faB fa8 Fab FaB Fa8 4ab 4aB 4a8
import java.util.ArrayList;
import java.util.HashMap;
//Given a hashmap M which is a mapping of characters to arrays of substitute characters,
//and an input string S, return an array of all possible mutations of S
//(where any character in S can be substituted with one of its substitutes in M, if it exists).
public class Permute {
public static ArrayList<String> getMutation(String str, HashMap<Character, char[]> map){
ArrayList<String> result = new ArrayList<String>();
int lens = str.length();
if(lens == 0){
return result;
}
if(map.isEmpty()){
result.add(str);
return result;
}
char[] mutation = new char[lens];
getMutation(str, map, result, mutation, 0);
return result;
}
public static void getMutation(String str, HashMap<Character, char[]> map, ArrayList<String> result, char[] mutation, int index){
if(index == str.length()){
String newItem = new String(mutation);
result.add(newItem);
return;
}
char current = str.charAt(index);
if(map.containsKey(current)){
char[] choice = map.get(current);
for(int i = 0; i <= choice.length;i++){
if(i == 0){
mutation[index] = current;
getMutation(str, map,result, mutation, index+1);
}
else{
mutation[index] = choice[i-1];
getMutation(str, map, result, mutation, index+1);
}
}
}
else{
mutation[index] = current;
getMutation(str, map, result, mutation, index+1);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
String in = "fab";
char[] valueOne = new char[2];
char[] valueTwo = new char[2];
HashMap<Character, char[]> map = new HashMap<Character, char[]>();
valueOne[0] = 'F';
valueOne[1] = '4';
valueTwo[0] = 'B';
valueTwo[1] = '8';
map.put('f', valueOne);
map.put('b', valueTwo);
ArrayList<String> result = new ArrayList<String>();
result = getMutation(in, map);
for(String str:result){
System.out.println(str);
}
}
}