題目描述

你需要采用前序遍歷的方式，將一個二叉樹轉(zhuǎn)換成一個由括號和整數(shù)組成的字符串。
空節(jié)點(diǎn)則用一對空括號 "()" 表示。而且你需要省略所有不影響字符串與原始二叉樹之間的一對一映射關(guān)系的空括號對。

官方題解

我們可以使用遞歸的方法得到二叉樹的前序遍歷。在遞歸時，根據(jù)題目描述，我們需要加上額外的括號，會有以下 4 種情況：

• 如果當(dāng)前節(jié)點(diǎn)有兩個孩子，那我們在遞歸時，需要在兩個孩子的結(jié)果外都加上一層括號；
• 如果當(dāng)前節(jié)點(diǎn)沒有孩子，那我們不需要在節(jié)點(diǎn)后面加上任何括號；
• 如果當(dāng)前節(jié)點(diǎn)只有左孩子，那我們在遞歸時，只需要在左孩子的結(jié)果外加上一層括號，而不需要給右孩子加上任何括號；
• 如果當(dāng)前節(jié)點(diǎn)只有右孩子，那我們在遞歸時，需要先加上一層空的括號 () 表示左孩子為空，再對右孩子進(jìn)行遞歸，并在結(jié)果外加上一層括號。

鏈接：https://leetcode-cn.com/problems/construct-string-from-binary-tree

實(shí)現(xiàn)

遞歸

復(fù)雜度

• 時間復(fù)雜度：O(N)，需要遍歷樹中N個節(jié)點(diǎn)
• 空間復(fù)雜度：O(N) ？？？

代碼

/**
 * 606. 根據(jù)二叉樹創(chuàng)建字符串
 *
 * 題目的意思是子節(jié)點(diǎn)需要用()來包裹。
 * 舉例來說，二叉樹[root,left,right]，則轉(zhuǎn)換為root(left)(right)。
 *
 * 1：如果只有l(wèi)eft為空節(jié)點(diǎn)，則輸出root()(right)
 * 2：如果只有right為空節(jié)點(diǎn)則可以忽略右節(jié)點(diǎn)的()，輸出為root(left)。
 * 3：如果過都不為空，則輸出為root(left)(right)
 * 3：如果左右都為空節(jié)點(diǎn)，則輸出root
 *
 * --------------------------------------------------------------
 *
 * 官方題解：
 * 我們可以使用遞歸的方法得到二叉樹的前序遍歷。在遞歸時，根據(jù)題目描述，我們需要加上額外的括號，會有以下 4 種情況：
 * 1：如果當(dāng)前節(jié)點(diǎn)有兩個孩子，那我們在遞歸時，需要在兩個孩子的結(jié)果外都加上一層括號；
 * 2：如果當(dāng)前節(jié)點(diǎn)沒有孩子，那我們不需要在節(jié)點(diǎn)后面加上任何括號；
 * 3：如果當(dāng)前節(jié)點(diǎn)只有左孩子，那我們在遞歸時，只需要在左孩子的結(jié)果外加上一層括號，而不需要給右孩子加上任何括號；
 * 4：如果當(dāng)前節(jié)點(diǎn)只有右孩子，那我們在遞歸時，需要先加上一層空的括號 () 表示左孩子為空，再對右孩子進(jìn)行遞歸，并在結(jié)果外加上一層括號。
 *
 * https://leetcode-cn.com/problems/construct-string-from-binary-tree/comments/
 */
public class LeetCode_606 {
    /**
     * 遞歸實(shí)現(xiàn)
     */
    public static String tree2str(TreeNode t) {
        StringBuilder sb = new StringBuilder();

        preOrderTraverse(t, sb);

        return sb.toString();
    }

    /**
     * 前序遍歷
     */
    private static void preOrderTraverse(TreeNode root, StringBuilder sb) {
        if (root == null) {
            return;
        }

        //添加跟節(jié)點(diǎn)內(nèi)容
        sb.append(root.val);

        if (root.left == null && root.right != null) { //左孩子為空,右孩子不為空
            sb.append("(");
            sb.append(")");

            sb.append("(");
            preOrderTraverse(root.right, sb);
            sb.append(")");

        } else if (root.left != null && root.right == null) { //左孩子不為空,右孩子為空
            sb.append("(");
            preOrderTraverse(root.left, sb);
            sb.append(")");

        } else if (root.left != null) { //左孩子不為空,右孩子不為空
            sb.append("(");
            preOrderTraverse(root.left, sb);
            sb.append(")");

            sb.append("(");
            preOrderTraverse(root.right, sb);
            sb.append(")");
        }
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}