資訊專欄INFORMATION COLUMN
摘要：題意從一顆二叉樹轉(zhuǎn)為帶括號的字符串。這題是的姊妹題型，該題目的解法在這里解法。
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]
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]
1
/
2 3
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.
題意: 從一顆二叉樹轉(zhuǎn)為帶括號的字符串。這題是LeetCode 536的姊妹題型，該題目的解法在這里L(fēng)eetCode 536解法。
解題思路：和536一樣，這題的括號的位置，字符串的結(jié)構(gòu)為root.val(root.left.val)(root.right.val)，當(dāng)left為空時，需要多加一個(), 我們循環(huán)DFS調(diào)用function, 先得到當(dāng)前的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();
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/71882.html
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...
摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...
摘要：題意從一個帶括號的字符串，構(gòu)建一顆二叉樹。其中當(dāng)而時，展示為一個空的括號。同時要考慮負(fù)數(shù)的情況，所以在取數(shù)字的時候，必須注意所在位置。遇到則從棧中出元素。最后中的元素就是，返回棧頂元素即可。 LeetCode 536. Construct Binary Tree from String You need to construct a binary tree from a string ...
摘要：有效三角形的個數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個數(shù)字?？偨Y(jié)本題和三數(shù)之和很像，都是三個數(shù)加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...
摘要：題目描述以為中心進(jìn)行分類題目分析根據(jù)中序和后序遍歷，構(gòu)造二叉樹。根據(jù)動態(tài)規(guī)劃方法，找出循環(huán)的共性。構(gòu)造子二叉樹，需要節(jié)點(diǎn)，和左右連接，從后序遍歷找出根節(jié)點(diǎn)，從對目標(biāo)序列進(jìn)行切分，如此往復(fù)。 題目描述： Given inorder and postorder traversal of a tree, construct the binary tree. Note: You may a...
閱讀 3684·2021-10-09 09:44
閱讀 3349·2021-09-22 15:29
閱讀 3117·2019-08-30 15:54
閱讀 3018·2019-08-29 16:19
閱讀 2142·2019-08-29 12:50
閱讀 595·2019-08-26 14:04
閱讀 1696·2019-08-23 18:39
閱讀 1345·2019-08-23 17:59
