2015年9月24日星期四

Print arbitrary binary tree by vertical levels / columns from left to right

example tree

      a
     / \
    b   c. more info on 1point3acres.com
   / \   \
  d   g   z
   \     /. visit 1point3acres.com for more.
    e   i
       /
      q. more info on 1point3acres.com
     /
    x
   /
  x1
/
x2

[x2]
[d, x1]
[b, e, x]
[a, g, q]
[c, i]
[z]

public void printTreeVertical(TreeNode node) {
if (node == null) return;
TreeMap<Integer, List<TreeNode>> treeMap = new TreeMap<Integer, List<TreeNode>>();
visit(node, 0, treeMap);
for (Entry<Integer, List<TreeNode>> entry : treeMap.entrySet()) {
for (TreeNode tmp : entry.getValue()) {
System.out.print(tmp.val);
}
System.out.println();
}
}

private void visit(TreeNode node, int column, TreeMap<Integer, List<TreeNode>> treeMap) {
if (node == null) {
return;
}
List<TreeNode> list = treeMap.get(column);
if (list == null) {
list = new ArrayList<TreeNode>();
treeMap.put(column, list);
}
list.add(node);
visit(node.left, column - 1, treeMap);
visit(node.right, column + 1, treeMap);
}

没有评论:

发表评论