Sponsored
Sponsored
This approach uses a recursive depth-first traversal starting from the root. For each node, construct the string representation by first adding the node's value. Then recursively obtain the string for the left and right subtrees. Handle empty parentheses carefully to meet problem constraints, particularly when a node has a right child but no left child.
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is visited once.
Space Complexity: O(h), where h is the height of the tree, due to the recursive call stack.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5typedef struct TreeNode {
6 int val;
7 struct TreeNode *left;
8 struct TreeNode *right;
9} TreeNode;
10
11char *tree2str(TreeNode *t) {
12 if (!t) return "";
13
14 char *left = tree2str(t->left);
15 char *right = tree2str(t->right);
16
17 char *res = (char *)malloc(10000 * sizeof(char));
18 sprintf(res, "%d", t->val);
19
20 if (strlen(left) || strlen(right)) {
21 strcat(res, "(");
22 strcat(res, left);
23 strcat(res, ")");
24 }
25 if (strlen(right)) {
26 strcat(res, "(");
27 strcat(res, right);
28 strcat(res, ")");
29 }
30 free(left);
31 free(right);
32 return res;
33}The code defines a function tree2str that recursively traverses the tree. For each node, it checks if there's a need to include the left and/or right children in the string. If a right child exists without a left child, it includes an empty set of parentheses before the right child. Memory allocation is handled dynamically to accommodate the resultant string's size, given the constraints. The function returns the constructed string after processing all nodes.
This approach leverages an iterative traversal using a stack to emulate the recursive call stack. This can be beneficial in languages without native recursion optimization or for learning alternative tree traversal methods. The stack helps manage nodes and their parents as we build the string representation iteratively.
Time Complexity: O(n)
Space Complexity: O(n), as the stack can store every node.
1class TreeNode:
2 def __init__(self, val=0, left=None,
The iterative Python solution uses a stack to manage tree traversal and construct the string. Each node's value is appended as we pop it from the stack. Special handling ensures proper insertion of parentheses to reflect tree structure accurately without recursion.