//reference: http://www.geeksforgeeks.org/print-nodes-top-view-binary-tree/
//Question: Is it possible to solve this problem using BFS?
package binaryTree.top.view;
import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
public class Solution {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
root.right.right = new TreeNode(7);
// TreeNode root = new TreeNode(1);//Used DFS first, caught a bug in
// this test case, change to BFS
// root.left = new TreeNode(2);
// root.right = new TreeNode(3);
// root.left.right = new TreeNode(4);
// root.left.right.right = new TreeNode(5);
// root.left.right.right.right = new TreeNode(6);
topView(root);
}
public static void topView(TreeNode root) {
if (root == null) {
return;
}
Deque<TreeNode> deque = new LinkedList<TreeNode>();
Set<Integer> set = new HashSet<Integer>();
Queue<QueueItem> queue = new LinkedList<QueueItem>();
queue.offer(new QueueItem(root, 0));
while (!queue.isEmpty()) {
QueueItem item = queue.poll();
if (item.node == null) {
continue;
}
if (!set.contains(item.order)) {
set.add(item.order);
if (item.order <= 0) {
deque.addFirst(item.node);
} else {
deque.addLast(item.node);
}
}
queue.offer(new QueueItem(item.node.left, item.order - 1));
queue.offer(new QueueItem(item.node.right, item.order + 1));
}
for (TreeNode t : deque) {
System.out.print(t.value);
System.out.print(" ");
}
}
}
package binaryTree.top.view;
public class QueueItem {
TreeNode node;
int order;
public QueueItem(TreeNode node, int order) {
this.node = node;
this.order = order;
}
}
package binaryTree.top.view;
public class TreeNode {
int value;
TreeNode left;
TreeNode right;
public TreeNode(int value) {
this.value = value;
}
}
没有评论:
发表评论