LeetCode 606. Construct String from Binary Tree 二叉

mikyou 發布于2019-08-16 13:31 / 1174人閱讀

摘要：題意從一顆二叉樹轉為帶括號的字符串。這題是的姊妹題型，該題目的解法在這里解法。

LeetCode 606. Construct String from Binary Tree

You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way.

The null node needs to be represented by empty parenthesis pair "()". And you need to omit all the empty parenthesis pairs that don"t affect the one-to-one mapping relationship between the string and the original binary tree.

Example 1:
Input: Binary tree: [1,2,3,4]

Output: "1(2(4))(3)"

Explanation: Originallay 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: Binary tree: [1,2,3,null,4]

Output: "1(2()(4))(3)"

Explanation: Almost the same as the first example,
except we can"t omit the first parenthesis pair to break the one-to-one mapping relationship between the input and the output.

題意: 從一顆二叉樹轉為帶括號的字符串。這題是LeetCode 536的姊妹題型，該題目的解法在這里LeetCode 536解法。

解題思路：和536一樣，這題的括號的位置，字符串的結構為root.val(root.left.val)(root.right.val)，當left為空時，需要多加一個(), 我們循環DFS調用function, 先得到當前的node的value，再得到左子樹的字符串，和右子樹的字符串，用StringBuilder鏈接起來，用""來判斷是否為空，其中值得注意的是- StringBuilder在初始化一個int值時，需要額外添+""，使得它為一個字符串，而不會解析成capacity。

StringBuilder(int initCapacity)
Creates an empty string builder with the specified initial capacity.

public String tree2str(TreeNode t) {
        if (t == null) {
            return "";
        }
        StringBuilder res = new StringBuilder(t.val+"");
        String left = tree2str(t.left);
        String right = tree2str(t.right);
        if (left.equals("") && right.equals("")) {
            return res.toString();
        }
        if (left.equals("") && !right.equals("")) {
            res.append("()(").append(right).append(")");
            return res.toString();
        }
        if (!left.equals("") && right.equals("")) {
            res.append("(").append(left).append(")");
            return res.toString();
        }
        res.append("(").append(left).append(")").append("(").append(right).append(")");
        return res.toString();
        
    }

GPU云服務器云服務器 binary-tree LeetCode_String binary-search-tree Construct

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/71882.html

[LeetCode] 606. Construct String from Binary Tree

Problem You need to construct a string consists of parenthesis and integers from a binary tree with the preorder traversing way. The null node needs to be represented by empty parenthesis pair (). And...

madthumb 2019-08-16 13:39 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 536. Construct Binary Tree from String 從帶

摘要：題意從一個帶括號的字符串，構建一顆二叉樹。其中當而時，展示為一個空的括號。同時要考慮負數的情況，所以在取數字的時候，必須注意所在位置。遇到則從棧中出元素。最后中的元素就是，返回棧頂元素即可。 LeetCode 536. Construct Binary Tree from String You need to construct a binary tree from a string ...

tabalt 2019-08-16 13:31 評論0 收藏0
LeetCode 精選TOP面試題【51 ~ 100】

摘要：有效三角形的個數雙指針最暴力的方法應該是三重循環枚舉三個數字。總結本題和三數之和很像，都是三個數加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復雜度為 ...

Clect 2021-11-15 11:38 評論0 收藏0
leetcode-106-根據中序和后序遍歷，構造二叉樹

摘要：題目描述以為中心進行分類題目分析根據中序和后序遍歷，構造二叉樹。根據動態規劃方法，找出循環的共性。構造子二叉樹，需要節點，和左右連接，從后序遍歷找出根節點，從對目標序列進行切分，如此往復。題目描述： Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may a...

widuu 2019-07-30 16:04 評論0 收藏0