2015年8月9日星期日

[吐槽][口袋宝石] Top View of Binary Tree

//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;
    }
}

没有评论:

发表评论