Last Updated on 2023-12-08 by Clay
題目
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
題目要求我們要按照 preorder 的順序遍歷整個樹狀結構並儲存成字串，也就是從右子節點一路向下走到底，回到上一層，開始走左邊... 簡單來說，使用 stack 或是 DFS 就能完成。
解題思路
正如上述，使用深度搜索（DFS）就可以正常解出這一題，不過題目還藏著一個小陷阱：那就是要求要在左節點不存在但右節點存在的情況下，把我們解析的字串中要把左節點加進來，變成一個空白的 () 符號。但是在左節點存在右節點不存在的情況，則不需要添加右節點的空白。
為了這個限制，我自己是多寫了一個判斷式。
C++ 範例程式碼
/**
* 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 範例程式碼
# 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