Problem
Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.
Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.
Example 1:
Input: root = [1,2,3,4] Output: “1(2(4))(3)” Explanation: Originally, it needs to be “1(2(4)())(3()())”, but you need to omit all the unnecessary empty parenthesis pairs. And it will be “1(2(4))(3)”
Example 2:
Input: root = [1,2,3,null,4] Output: “1(2()(4))(3)” Explanation: Almost the same as the first example, except we cannot omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.
Constraints:
- The number of nodes in the tree is in the range
[1, 104]. -1000 <= Node.val <= 1000
The problem hope us to follow the preorder to traversal the tree structure and save to string. That means we need to visit the right node first, to the last layer and then return the previous layer, start to the left side… simply put, we can use stack or DFS to solve it.
Solution
Like I said above, we can use depth first search to solve the problem, but put attention for a simple trap: The problem ask us to create a null () if the left node does not exist but right does! But if the left node exists and right node not exists, we don’t add this null ().
So, I insert a additional if-else line to determine.
C++ Sample Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
string tree2str(TreeNode* root) {
// Init
string s = std::to_string(root->val);
// If left node is exists.
if (root->left != nullptr) {
s += '(';
s += tree2str(root->left);
s += ')';
}
// If left node does not exist but right does.
else if (root->right != nullptr) {
s += "()";
}
// If right node is exists.
if (root->right != nullptr) {
s += '(';
s += tree2str(root->right);
s += ')';
}
return s;
}
};Python Sample Code
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def tree2str(self, root: Optional[TreeNode]) -> str:
# Init
s = str(root.val)
# If left node is exists.
if root.left:
s += f"({self.tree2str(root.left)})"
# If left node does not exist but right does.
elif root.right:
s += "()"
# If right node is exists.
if root.right:
s += f"({self.tree2str(root.right)})"
return s