diff options
author | Jack Sangdahl <[email protected]> | 2025-09-02 09:07:00 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-09-02 09:07:00 -0600 |
commit | 44bca90a777b14e8dc145f92f13a760b6949aeae (patch) | |
tree | 340b0baaa1ac46280e6815f565ddc249d29ebd1f /print_binary_tree.py | |
parent | 57914ff67da704020301e06ab036c92c81ee85ab (diff) | |
download | leetcode-44bca90a777b14e8dc145f92f13a760b6949aeae.tar.gz leetcode-44bca90a777b14e8dc145f92f13a760b6949aeae.zip |
655. print binary tree
Diffstat (limited to 'print_binary_tree.py')
-rw-r--r-- | print_binary_tree.py | 47 |
1 files changed, 47 insertions, 0 deletions
diff --git a/print_binary_tree.py b/print_binary_tree.py new file mode 100644 index 0000000..3c2b147 --- /dev/null +++ b/print_binary_tree.py @@ -0,0 +1,47 @@ +# 655. Print Binary Tree +from leetcode import treenode_build + +""" +given the 'root' of a binary tree, construct a 0-indexed 'm x n' string +matrix 'res' that represents a formatted layout of the tree. the formatted +layout matrix should be constructed using the following rules. the height of +the tree is 'height' and the number of rows 'm' should be equal to 'height + +1'. the number of columns 'n' should be equal to '2^(height + 1) - 1'. place +the root node in the middle of the top row (more formally, at location +'res[0][(n - 1) / 2]'). continue this process until all the nodes in the tree +have been placed. any empty cells should contain the empty string "". return +the constructed matrix 'res'. +""" + + +class Solution(object): + def printTree(self, root): + """ + :type root: Optional[TreeNode] + :rtype: List[List[str]] + """ + + def height(node): + return 0 if not node else 1 + max(height(node.left), height(node.right)) + + def build(node, row, left, right): + if not node: + return + mid = (left + right) / 2 + self.grid[row][mid] = str(node.val) + build(node.left, row + 1, left, mid - 1) + build(node.right, row + 1, mid + 1, right) + + h = height(root) + w = 2**h - 1 + self.grid = [[""] * w for i in range(h)] + build(node=root, row=0, left=0, right=w - 1) + return self.grid + + +if __name__ == "__main__": + obj = Solution() + r1 = treenode_build(vals=[1, 2]) + r2 = treenode_build(vals=[1, 2, 3, None, 4]) + print(obj.printTree(r1)) + print(obj.printTree(r2)) |