package com.biplav.algorithms;
public class FlattenBST {
public static class TreeNode {
public TreeNode left;
public TreeNode right;
public int value;
public TreeNode(TreeNode left, TreeNode right, int value) {
super();
this.left = left;
this.right = right;
this.value = value;
}
}
public static class ListNode {
public ListNode next;
public int value;
public ListNode(ListNode next, int value) {
super();
this.next = next;
this.value = value;
}
}
public static ListNode flatten(TreeNode root) {
ListNode left = root.left != null ? flatten(root.left) : null;
ListNode base = new ListNode(null,root.value);
ListNode right = root.right != null ? flatten(root.right) : null;
base.next = right != null ? right : null;
if(left == null) return base;
else {
ListNode home = left;
while(left.next != null) left = left.next;
left.next= base;
return home;
}
}
/*
* 6
* 3 8
* 2 4 7 10
*/
public static void main(String[] args) {
TreeNode t3 = new TreeNode(null, null, 2);
TreeNode t2 = new TreeNode(null, null, 4);
TreeNode t4 = new TreeNode(t3, t2, 3);
TreeNode t7 = new TreeNode(null, null, 7);
TreeNode t10 = new TreeNode(null, null, 10);
TreeNode t8 = new TreeNode(t7, t10, 8);
TreeNode t6 = new TreeNode(t4, t8, 6);
ListNode root = flatten(t6);
while(root != null) {
System.out.println(root.value);
root = root.next;
}
}
}
Comments
Post a Comment