aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-09-02 09:07:00 -0600
committerJack Sangdahl <[email protected]>2025-09-02 09:07:00 -0600
commit44bca90a777b14e8dc145f92f13a760b6949aeae (patch)
tree340b0baaa1ac46280e6815f565ddc249d29ebd1f
parent57914ff67da704020301e06ab036c92c81ee85ab (diff)
downloadleetcode-44bca90a777b14e8dc145f92f13a760b6949aeae.tar.gz
leetcode-44bca90a777b14e8dc145f92f13a760b6949aeae.zip
655. print binary tree
-rw-r--r--print_binary_tree.c84
-rw-r--r--print_binary_tree.py47
2 files changed, 131 insertions, 0 deletions
diff --git a/print_binary_tree.c b/print_binary_tree.c
new file mode 100644
index 0000000..6d89e6b
--- /dev/null
+++ b/print_binary_tree.c
@@ -0,0 +1,84 @@
+// 655. Print Binary Tree
+#include "leetcode.h"
+
+/*
+ * 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'.
+ */
+
+#define STR_LEN 10
+
+int height(struct TreeNode *node) {
+ if (!node)
+ return -1;
+ return 1 + fmax(height(node->left), height(node->right));
+}
+
+void build(struct TreeNode *node, char ***grid, int h, int r, int c) {
+ if (!node)
+ return;
+ sprintf(grid[r][c], "%d", node->val);
+ build(node->left, grid, h, r + 1, c - (int)pow(2, h - r - 1));
+ build(node->right, grid, h, r + 1, c + (int)pow(2, h - r - 1));
+}
+
+char ***new_grid(size_t m, size_t n) {
+ char ***res = (char ***)malloc(m * sizeof(char **));
+ for (int i = 0; i < m; i++) {
+ res[i] = (char **)malloc(n * sizeof(char *));
+ for (int j = 0; j < n; j++) {
+ res[i][j] = (char *)calloc(STR_LEN, sizeof(char));
+ strcat(res[i][j], ""
+ "");
+ }
+ }
+ return res;
+}
+
+char ***printTree(struct TreeNode *root, int *returnSize,
+ int **returnColumnSizes) {
+ int h = height(root), m = h + 1, n = (1 << (h + 1)) - 1;
+ char ***grid = new_grid(m, n);
+ build(root, grid, h, 0, (n - 1) / 2);
+ *returnSize = m;
+ *returnColumnSizes = (int *)malloc(m * sizeof(int));
+ for (int i = 0; i < m; i++)
+ *returnColumnSizes[i] = n;
+ return grid;
+}
+
+int main() {
+ int r1i[] = {1, 2}, rs1, *rcs1;
+ int r2i[] = {1, 2, 3, -1, 4}, rs2, *rcs2;
+ struct TreeNode *r1 = treenode_build(r1i, ARRAY_SIZE(r1i));
+ struct TreeNode *r2 = treenode_build(r2i, ARRAY_SIZE(r2i));
+ char ***pt1 = printTree(r1, &rs1, &rcs1);
+ char ***pt2 = printTree(r2, &rs2, &rcs2);
+ for (int i = 0; i < rs1; i++) {
+ for (int j = 0; j < rcs1[i]; j++)
+ printf("%s ", pt1[i][j]);
+ printf("\n");
+ }
+ for (int i = 0; i < rs2; i++) {
+ for (int j = 0; j < rcs2[i]; j++)
+ printf("%s ", pt2[i][j]);
+ printf("\n");
+ }
+ for (int i = 0; i < rs1; i++)
+ free(pt1[i]);
+ free(pt1);
+ free(rcs1);
+ treenode_free(r1);
+ for (int i = 0; i < rs2; i++)
+ free(pt2[i]);
+ free(pt2);
+ free(rcs2);
+ treenode_free(r2);
+}
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))