Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists)
My initial thoughts:
We just do a level-order traversal throughout the tree. For each level, create a linked list containing all the nodes at that depth. Then extract all of the children for each node to create the next linked list at deeper level.
My initial codes:
public static List<LinkedList<BinaryTreeNode>> createLinkedLists( BinaryTreeNode root) { List<LinkedList<BinaryTreeNode>> lists = new ArrayList<LinkedList<BinaryTreeNode>>(); LinkedList<BinaryTreeNode> level0 = new LinkedList<BinaryTreeNode>(); level0.add(root); lists.add(level0); int index = 0; while (true) { LinkedList<BinaryTreeNode> leveli = new LinkedList<BinaryTreeNode>(); LinkedList<BinaryTreeNode> upperLevel = lists.get(index); for (int i = 0; i < upperLevel.size(); ++i) { BinaryTreeNode parent = upperLevel.get(i); leveli.add(parent.getLeft()); leveli.add(parent.getRight()); } if (!leveli.isEmpty()) { lists.add(leveli); index++; } else { break; } } return lists; }Comments after running:
NullPointerException in highlighted line 14 and 15. Need to check whether left or right exists before putting into the linked-list. Correction:if (parent.getLeft() != null) leveli.add(parent.getLeft()); if (parent.getRight() != null) leveli.add(parent.getRight());Solution:
The solution is identical to my codes:public static ArrayList<LinkedList<BinaryTreeNode>> findLevelLinkList( BinaryTreeNode root) { int level = 0; ArrayList<LinkedList<BinaryTreeNode>> result = new ArrayList<LinkedList<BinaryTreeNode>>(); LinkedList<BinaryTreeNode> list = new LinkedList<BinaryTreeNode>(); list.add(root); result.add(level, list); while (true) { list = new LinkedList<BinaryTreeNode>(); for (int i = 0; i < result.get(level).size(); i++) { BinaryTreeNode n = result.get(level).get(i); if (n != null) { if (n.getLeft() != null) list.add(n.getLeft()); if (n.getRight() != null) list.add(n.getRight()); } } if (list.size() > 0) { result.add(level + 1, list); } else { break; } level++; } return result; }Advertisements