grid47 Exploring patterns and algorithms
Sep 2, 2024
7 min read
Solution to LeetCode 655: Print Binary Tree Problem
Given the root of a binary tree, construct a matrix representation of the tree using specific formatting rules to place each node in the appropriate position in the matrix.
Problem
Approach
Steps
Complexity
Input: The input is the root of a binary tree represented as an array of nodes.
Example: root = [10, 5, 15, null, 7]
Constraints:
• The number of nodes in the tree is in the range [1, 210].
• -99 <= Node.val <= 99
• The depth of the tree will be in the range [1, 10].
Output: The output is a 0-indexed matrix representing the binary tree, formatted according to the specified rules.
• The output matrix will be of size m x n, where m is the height of the tree + 1 and n is 2^height + 1 - 1.
Goal: The goal is to recursively place each node in its appropriate position in the matrix based on the rules provided.
Steps:
• 1. Calculate the height of the tree.
• 2. Calculate the width of the matrix using the tree height.
• 3. Recursively place the root node and its children in the matrix.
• 4. Fill in the left and right children by adjusting their positions accordingly in each row.
Goal: The tree will have a depth between 1 and 10, with node values between -99 and 99, and there will be no more than 210 nodes.
Steps:
• 1 <= number of nodes <= 210
• -99 <= Node.val <= 99
• Tree depth between 1 and 10
Assumptions:
• The input will always be a valid binary tree with nodes having unique values.
• Input: root = [10, 5, 15, null, 7]
• Explanation: The root node `10` is placed in the center of the matrix. Its children, `5` and `15`, are placed in subsequent rows, with `7` placed as the child of `15`.
Approach: This problem can be solved by recursively placing each node at the appropriate position in a matrix based on the tree's structure.
Observations:
• This problem requires calculating the matrix dimensions based on the tree's height and recursively placing nodes.
• Recursive placement of nodes will involve carefully calculating the middle index of each row and adjusting for left and right children.
Steps:
• 1. Calculate the height of the tree using a recursive function.
• 2. Calculate the width of the matrix using the height.
• 3. Create the matrix and fill it with empty strings.
• 4. Define a helper function that places each node at its correct position in the matrix and handles left and right children.
Empty Inputs:
• The tree will always contain at least one node.
Large Inputs:
• For trees with the maximum number of nodes, the solution should still function efficiently.
Special Values:
• The tree can have negative and zero values, which should be handled appropriately.
Constraints:
• Ensure that all nodes are placed correctly based on their position in the matrix.
vector<vector<string>> printTree(TreeNode* root) {
int h = get_height(root), w = get_width(root);
vector<vector<string>> ans(h, vector<string>(w, ""));
helper(ans, root, 0, 0, w -1);
return ans;
}
intget_height(TreeNode *p) {
if(!p) return0;
int left = get_height(p->left);
int right = get_height(p->right);
return max(left , right) +1;
}
intget_width(TreeNode *p) {
if(!p) return0;
int left = get_width(p->left);
int right = get_width(p->right);
return max(left, right)*2+1;
}
voidhelper(vector<vector<string>>&ans, TreeNode *p, int level, int l, int r) {
if(!p) return;
int mid = l + (r - l)/2;
ans[level][mid] = to_string(p->val);
helper(ans, p->left, level +1, l, mid -1);
helper(ans, p->right, level +1, mid +1, r);
}
};
This is the header of the `printTree` function, which takes a pointer to the root of a binary tree and returns a 2D vector of strings representing the tree.
2 : Height and Width Calculation
int h = get_height(root), w = get_width(root);
The height and width of the tree are calculated using the `get_height` and `get_width` functions. These values define the dimensions of the 2D array that will hold the tree values.
A 2D vector `ans` is initialized with dimensions `h` and `w`, where `h` is the height and `w` is the width of the tree. The vector is filled with empty strings to represent the unoccupied spaces.
4 : Helper Function Call
helper(ans, root, 0, 0, w -1);
The `helper` function is called to fill in the 2D vector with the values of the nodes at the correct positions.
5 : Return Result
return ans;
The 2D vector `ans` is returned, which now contains the visual representation of the binary tree.
6 : Get Tree Height
intget_height(TreeNode *p) {
The `get_height` function calculates the height of a binary tree. It is used in the `printTree` function to determine the number of rows needed in the output.
7 : Base Case
if(!p) return0;
If the current node is null, the height is 0.
8 : Recursive Height Calculation
int left = get_height(p->left);
Recursively calculate the height of the left subtree.
9 : Recursive Height Calculation
int right = get_height(p->right);
Recursively calculate the height of the right subtree.
10 : Return Height
returnmax(left , right) +1;
The height of the current tree is the maximum of the left and right subtree heights, plus 1 for the current node.
11 : Get Tree Width
intget_width(TreeNode *p) {
The `get_width` function calculates the width of a binary tree. It is used in the `printTree` function to determine the number of columns needed in the output.
12 : Base Case
if(!p) return0;
If the current node is null, the width is 0.
13 : Recursive Width Calculation
int left = get_width(p->left);
Recursively calculate the width of the left subtree.
14 : Recursive Width Calculation
int right = get_width(p->right);
Recursively calculate the width of the right subtree.
15 : Return Width
returnmax(left, right)*2+1;
The width of the tree is calculated as the maximum width of the left and right subtrees multiplied by 2, plus 1 for the current node.
16 : Helper Function
voidhelper(vector<vector<string>>&ans, TreeNode *p, int level, int l, int r) {
The `helper` function is a recursive function that fills the 2D vector `ans` with node values at the correct positions based on the tree structure.
17 : Base Case
if(!p) return;
If the current node is null, the function returns without making changes.
18 : Calculate Middle Position
int mid = l + (r - l)/2;
The middle column index is calculated to position the current node in the 2D vector.
19 : Place Node Value
ans[level][mid] = to_string(p->val);
The value of the current node is placed in the 2D vector `ans` at the calculated middle position.
20 : Left Subtree
helper(ans, p->left, level +1, l, mid -1);
Recursively call the helper function to place the left child in the appropriate position.
21 : Right Subtree
helper(ans, p->right, level +1, mid +1, r);
Recursively call the helper function to place the right child in the appropriate position.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the number of nodes in the tree.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the recursion stack and the matrix storage.
