The Question is this:
6
/ \
3 5
/ \ \
2 5 4
/ \
7 4
There are 4 leaves, hence 4 root to leaf paths:
Path Sum
6->3->2 632
6->3->5->7 6357
6->3->5->4 6354
6->5>4 654
Expected Answer: 632+6357+6354+654=13997
The Program is this:
public class Main {
public static void main(String[] args) {
BinaryTree T = new BinaryTree(6);
T.specialInsert();
int answer = new AddLinkedListContnents().addLinkedLists(T.rootToLeaf());
System.out.println("answer="+answer);
}
}
//--------------------------------------------------------------------------------------------
import java.util.ArrayList;
public class BinaryTree {
BinaryTree left, right;
int data;
public BinaryTree(int data) {
this.data=data;
this.left=null;
this.right=null;
}
public void specialInsert() {
/* 6
/ \
3 5
/ \ \
2 5 4
/ \
7 4 */
BinaryTree T = this;
T.left=new BinaryTree(3);
T.left.left=new BinaryTree(2);
T.left.right=new BinaryTree(5);
T.left.right.left=new BinaryTree(7);
T.left.right.right=new BinaryTree(4);
T.right=new BinaryTree(5);
T.right.right=new BinaryTree(4);
}
private ArrayList<LinkedList> ArrList;
public ArrayList<LinkedList> rootToLeaf() {
ArrList=new ArrayList<LinkedList>();
rootToLead(this, new ArrayList<Integer>());
for(LinkedList L:ArrList) {
L.printList();
}
return ArrList;
}
private void rootToLead(BinaryTree T, ArrayList<Integer> path) {
if(T!=null) {
path.add(T.data);
if(T.left==null && T.right==null) {
ArrList.add(new LinkedList(path));
} else {
rootToLead(T.left, new ArrayList<>(path));
rootToLead(T.right, new ArrayList<>(path));
}
}
}
}
//--------------------------------------------------------------------------------------------
import java.util.ArrayList;
import java.util.Collections;
public class LinkedList {
LinkedList next;
int data;
private int size;
public LinkedList(int data) {
this.data=data;
this.next=null;
this.size++;
}
public LinkedList(ArrayList<Integer> values) {
Collections.reverse(values);
//Inserts Values in reverse
this.data=values.get(0);
this.next=null;
this.size++;
insert(values);
}
private void insert(ArrayList<Integer> values) {
int size = values.size();
if(size>0) {
LinkedList L = this;
for(int i=1; i<size; i++) {
L.next=new LinkedList(values.get(i));
L=L.next;
this.size++;
}
}
}
public void insert(int data) {
LinkedList L = this;
while(L!=null)
L=L.next;
L.next=new LinkedList(data);
this.size++;
}
public void printList() {
LinkedList L = this;
StringBuffer sb = new StringBuffer();
while(L!=null) {
sb.append(L.data).append(", ");
L=L.next;
}
System.out.println(sb.toString());
}
public int getSize() {
return size;
}
/*public void setSize(int size) {
this.size = size;
}*/
}
//--------------------------------------------------------------------------------------------
import java.util.ArrayList;
public class AddLinkedListContnents {
public int addLinkedLists(ArrayList<LinkedList> ALs) {
int LargestArraySize=FindLargestArraySize(ALs);
int carry = 0;
StringBuffer sb = new StringBuffer();
for(int i=0; i<LargestArraySize; i++) {
int current_sum = carry;
int size = ALs.size();
for(int j=0; j<size; j++) {
if(ALs.get(j)!=null) {
current_sum=current_sum+ALs.get(j).data;
ALs.set(j, ALs.get(j).next);
}
}
carry=current_sum/10;
current_sum=current_sum%10;
sb.append(current_sum);
current_sum=0;
}
sb.append(carry);
return Integer.parseInt(sb.reverse().toString());
}
private int FindLargestArraySize(ArrayList<LinkedList> ALs) {
int size=0;
for(LinkedList L:ALs) {
if(size<L.getSize())
size=L.getSize();
}
return size;
}
}
//--------------------------------------------------------------------------------------------
No comments:
Post a Comment