Skip to content

LeetCode: 606-Construct String from Binary Tree 解題紀錄

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

References


Read More

Leave a Reply取消回覆

Exit mobile version