Question Name: Print Tree By Columns

Question: print tree by columns, from leftmost column to rightmost column. For each node in i(th) column, if son(s) exist, its left son is in the (i-1)th column, and right son in the (i+1)th column.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | # Definition for a binary tree node. # For simplification, we use binary tree to demo the algorithm. # But any kind of trees, it should work well. class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def __str__(self, ind = 0): res = "t"*ind + str(self.val) + "n" if self.left == None: res += "t"*(ind+1) + "None" + "n" else: res += self.left.__str__(ind+1) if self.right == None: res += "t"*(ind+1) + "None" + "n" else: res += self.right.__str__(ind+1) return res @staticmethod def printByColumn(root): if root == None: print "Empty Tree." return assert isinstance(root, TreeNode) stack = [[root, 0]] # Used for preorder traversal # We will assign every column an index. The column, including root # is 0. All the columns, on the right of the 0 column, have an # positive index in increasing order. Similarly, all the columns, # on the left side, have a negative index in decreasing order. # # The columns' indexes are in a continue range. For example, in our # test case, the indexes are -2, -1, 0, 1, 2. To avoid the possible # insert operation on array, whose time complexity is O(N), we divide # the array to record the columns into two arrays. So that we only # need append operation on arrays, whose time is O(1). # Ref: https://wiki.python.org/moin/TimeComplexity nonNegativeColumns = [] negativeColumns = [] # Do a preorder traversal. Actually, any kind of traversal will # work well for this challenge. while len(stack) != 0: current = stack.pop() if current[1] >= 0: # On the right side of the root column. Or in the root column. if len(nonNegativeColumns) == current[1]: # First element of this column nonNegativeColumns.append([]) nonNegativeColumns[current[1]].append(current[0].val) else: # On the left side of the root column. if len(negativeColumns) == -current[1]-1: # First element of this column negativeColumns.append([]) negativeColumns[-current[1]-1].append(current[0].val) # Prepare to access the right son, if exists if current[0].right != None: stack.append([current[0].right, current[1]+1]) # Prepare to access the left son, if exists if current[0].left != None: stack.append([current[0].left, current[1]-1]) # Print the columns from the leftmost to rightmost for column in negativeColumns[::-1]: print " ".join(column) for column in nonNegativeColumns: print " ".join(column) return def main(): # Make the test case root = TreeNode("a") root.left = TreeNode("b") root.right = TreeNode("c") root.right.left = TreeNode("d") root.right.left.left = TreeNode("e") root.right.left.left.left = TreeNode("f") TreeNode.printByColumn(root) if __name__ == "__main__": main() |