LeetCode演算法題-Construct String from Binary Tree（Java實現）
這是悅樂書的第273 次更新，第288 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第141題（順位題號是606）。構造一個字串，該字串由二叉樹中的括號和整陣列成，並具有前序遍歷方式。null節點需要用空括號對“（）”表示。 並且你需要省略所有不影響字串與原始二叉樹之間的一對一對映關係的空括號對。例如：
輸入：二叉樹：[1,2,3,4]
1 /\ 23 / 4
輸出：“1（2（4））（3）”
說明：原始字串需要為“1（2（4）（））（3（）（））”，但是需要省略所有不必要的空括號對，所以是“1（2（4））（3）”。
輸入：二叉樹：[1,2,3，null，4]
1 / \ 23 \ 4
輸出：“1（2（）（4））（3）”
說明：與第一個示例幾乎相同，但是不能省略第一個括號對來打破輸入和輸出之間的一對一對映關係。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
題目有兩點要求，一是前序遍歷二叉樹，二是使用括號將節點值串起來。同時，對於第二點又可以細分為兩種情況，一是如果節點本身沒有左右子節點，就不必使用括號；二是如果節點本身的左子節點不為空，右子節點為空，那麼我們需要省掉右子節點的括號，直接對其左子節點繼續處理。
使用遞迴的方式，如果當前節點為空，直接返回空串；如果當前節點不存在左右子節點，直接返回當前節點值的字串；如果當前節點的左子節點不為空，右子節點為空，直接返回當前節點值與其左子節點的後續遞迴結果，其中左子節點前後需用括號。
剩下就是正常的情況，先處理根節點的值，再處理左子樹，使用括號包起來，最後處理右子樹，同樣使用括號包起來。
/**
* Definition for a binary tree node.
* public class TreeNode {
*int val;
*TreeNode left;
*TreeNode right;
*TreeNode(int x) { val = x; }
* }
*/
class Solution {
public String tree2str(TreeNode t) {
String result = preOrder(t);
return result;
}
public String preOrder(TreeNode t){
if (t == null) {
return "";
}
if (t.left == null && t.right == null) {
return t.val+"";
}
if (t.right == null) {
return t.val + "("+ preOrder(t.left)+")";
}
StringBuilder sb = new StringBuilder();
sb.append(t.val);
String s = preOrder(t.left);
sb.append("("+s+")");
String s2 = preOrder(t.right);
sb.append("("+s2+")");
return sb.toString();
}
}
03 第二種解法
我們可以把上面的寫法簡化下，在一個方法裡面完成，並且去掉StringBuilder類操作字串，直接使用連線符拼接。
/**
* Definition for a binary tree node.
* public class TreeNode {
*int val;
*TreeNode left;
*TreeNode right;
*TreeNode(int x) { val = x; }
* }
*/
class Solution {
public String tree2str(TreeNode t) {
if (t == null) {
return "";
}
if (t.left == null && t.right == null) {
return t.val+"";
}
if (t.right == null) {
return t.val + "("+ tree2str(t.left)+")";
}
return t.val + "("+tree2str(t.left)+ ")" + "(" + tree2str(t.right) + ")";
}
}
04 第三種解法
我們也可以使用迭代的方式。使用迭代的方式，首先要藉助棧，遍歷的順序為根節點，右子樹，左子樹，因為棧先進後出的特性，所以要先處理右子樹，其次我們還需要考慮括號的拼接順序問題。
如果直接使用前後括號拼接，會發現尾括號少了一部分，那麼我們需要藉助另外一個物件來判斷什麼時候該加尾部空格。對此，我們使用HashSet，存放已經訪問過的節點，並且原先直接出棧的方法要換成獲取棧頂的節點但是不出棧，只有都訪問過了，才會出棧並追加尾部括號，另外一種特殊情況當前節點左子節點為空，右子節點不為空，直接追加一個空括號即可。
遍歷完所有節點後，根據題目的要求，會發現字串頭部和尾部都多了一個單括號，所以要擷取字串，去掉頭尾的單括號。
/**
* Definition for a binary tree node.
* public class TreeNode {
*int val;
*TreeNode left;
*TreeNode right;
*TreeNode(int x) { val = x; }
* }
*/
class Solution {
public String tree2str(TreeNode t) {
if (t == null) {
return "";
}
if (t.left == null && t.right == null) {
return t.val+"";
}
Stack<TreeNode> stack = new Stack<TreeNode>();
Set<TreeNode> visited = new HashSet<TreeNode>();
String result = "";
stack.push(t);
while (!stack.isEmpty()) {
TreeNode temp = stack.peek();
if (visited.contains(temp)) {
stack.pop();
result += ")";
} else {
visited.add(temp);
result += "(" + temp.val;
if (temp.left == null && temp.right != null) {
result += "()";
}
if (temp.right != null) {
stack.push(temp.right);
}
if (temp.left != null) {
stack.push(temp.left);
}
}
}
return result.substring(1, result.length()-1);
}
}
05 小結
演算法專題目前已日更超過四個月 ，演算法題文章141 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！