LeetCode-606. 根据二叉树创建字符串

题目描述

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。
空节点则用一对空括号 "()" 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

官方题解

我们可以使用递归的方法得到二叉树的前序遍历。在递归时，根据题目描述，我们需要加上额外的括号，会有以下 4 种情况：

• 如果当前节点有两个孩子，那我们在递归时，需要在两个孩子的结果外都加上一层括号；
• 如果当前节点没有孩子，那我们不需要在节点后面加上任何括号；
• 如果当前节点只有左孩子，那我们在递归时，只需要在左孩子的结果外加上一层括号，而不需要给右孩子加上任何括号；
• 如果当前节点只有右孩子，那我们在递归时，需要先加上一层空的括号 () 表示左孩子为空，再对右孩子进行递归，并在结果外加上一层括号。

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

实现

递归

复杂度

• 时间复杂度：O(N)，需要遍历树中N个节点
• 空间复杂度：O(N) ？？？

代码

/**
 * 606. 根据二叉树创建字符串
 *
 * 题目的意思是子节点需要用()来包裹。
 * 举例来说，二叉树[root,left,right]，则转换为root(left)(right)。
 *
 * 1：如果只有left为空节点，则输出root()(right)
 * 2：如果只有right为空节点则可以忽略右节点的()，输出为root(left)。
 * 3：如果过都不为空，则输出为root(left)(right)
 * 3：如果左右都为空节点，则输出root
 *
 * --------------------------------------------------------------
 *
 * 官方题解：
 * 我们可以使用递归的方法得到二叉树的前序遍历。在递归时，根据题目描述，我们需要加上额外的括号，会有以下 4 种情况：
 * 1：如果当前节点有两个孩子，那我们在递归时，需要在两个孩子的结果外都加上一层括号；
 * 2：如果当前节点没有孩子，那我们不需要在节点后面加上任何括号；
 * 3：如果当前节点只有左孩子，那我们在递归时，只需要在左孩子的结果外加上一层括号，而不需要给右孩子加上任何括号；
 * 4：如果当前节点只有右孩子，那我们在递归时，需要先加上一层空的括号 () 表示左孩子为空，再对右孩子进行递归，并在结果外加上一层括号。
 *
 * https://leetcode-cn.com/problems/construct-string-from-binary-tree/comments/
 */
public class LeetCode_606 {
    /**
     * 递归实现
     */
    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;
        }

        //添加跟节点内容
        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;
        }
    }
}