打印所有路径的二叉树
问题描述:
以下设计是否可以进一步优化?我使用了一个hashmap和一个Queue。 SO空间复杂度将是O(n)和运行时会为O(n)打印所有路径的二叉树
public class PrintAllRootToLeaves {
public static void print(BinaryTreeNode root) {
Queue nodesQ = new Queue();
HashMap hMap = new HashMap();
BinaryTreeNode head = root;
String tempVal ;
hMap.put(head,String.valueOf(head.getData()));
while (head != null) {
BinaryTreeNode left = head.getLeft();
BinaryTreeNode right = head.getRight();
if (left != null) {
if ((tempVal = (String) hMap.get(head)) != null) {
hMap.put(left,tempVal + left.getData());
}
nodesQ.enqueue(left);
}
if (right != null) {
if ((tempVal = (String) hMap.get(head)) != null) {
hMap.put(right,tempVal + right.getData());
}
nodesQ.enqueue(right);
}
if (right != null && left != null) {
hMap.remove(head);
}
head = (BinaryTreeNode) nodesQ.dequeue();
}
System.out.println("-----------Printing all routes ---------->" + hMap.values());
}
}
答
public class BinaryTree {
private class Node {
final int key;
final int value;
Node left;
Node Right;
public Node (Node node, int pKey, int qValue) {
key = pKey;
value = qValue;
if (node != null && node.key < pKey) {
left = node;
}
else if (node != null) {
Right = node;
}
}
}
public void preOrderTraversal(Node pNode,String path){
if (path == null) {
path = "";
}
if (pNode != null) {
path = path+" "+String.valueOf(pNode.key);
//If you remove the modulo check it will print all the paths.
if (pNode.key%5 == 0) {
System.out.println(path);
}
preOrderTraversal(pNode.left,path);
preOrderTraversal(pNode.Right,path);
}
}
/**
* @param args
*/
public static void main(String[] args) {
Node node1 = new BinaryTree().new Node(null, 5, 2);
Node node2 = new BinaryTree().new Node(null, 10, 25);
Node node3 = new BinaryTree().new Node(node1, 7, 50);
node3.Right = node2;
Node root = new BinaryTree().new Node(node3, 15, 6);
Node node4 = new BinaryTree().new Node(null, 30, 8);
Node node5 = new BinaryTree().new Node(node4, 20, 7);
root.Right = node5;
//This will print paths only divisable by 5
new BinaryTree().preOrderTraversal(root,null);
}
}
+0
这是如何回答这个问题的? – 2013-08-01 03:06:04
看样子你需要遍历每个节点,所以我看不到复杂性如何为O少( N)。你可以做的是使用StringBuilder,而不是附加到一个字符串。 – 2012-08-13 14:26:16
你为什么要从循环中的散列表中删除节点,你是否只打印最低的树节点? – 2012-08-13 14:28:17
这不能在'O(N * Log N)'下完成,因为你有'N * Log N'项目需要打印。 – dasblinkenlight 2012-08-13 14:37:32