根据二叉树创建字符串

今天药忘吃喽~ 2023-10-10 15:09 17阅读 0赞

![ced485cbb11e458d81a746890b32cf3f.gif][]

> 作者：敲代码の流川枫
> 
> 博客主页：[流川枫的博客][Link 1]
> 
> 专栏：[和我一起学java][java]
> 
> 语录：Stay hungry stay foolish
> 
> 工欲善其事必先利其器，给大家介绍一款超牛的斩获大厂offer利器——牛客网
> 
> [点击注册和我一起刷题][Link 2]

> 给你二叉树的根节点 `root` ，请你采用前序遍历的方式，将二叉树转化为一个由括号和整数组成的字符串，返回构造出的字符串。
> 
> 空节点使用一对空括号对 `"()"` 表示，转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。![e68c41710339407bad76d70bd931af42.png][]
> 
> ![379dfb619610441cb2623a6f13ca2879.png][]

由题意可知我们要拼接一个字符串，先将根节点拼接

生成字符串的规则其实就是在「前序遍历」输出节点值的同时，在每颗子树的左右添加一对 ()（根节点除外），同时需要忽略掉一些不必要的 () 。

所谓的不必要就是指当以某个节点 xxx 为根时，其只「有左子树」而「没有右子树」时，右子树的 () 可被忽略，或者「左右子树都没有」时，两者的 () 可被忽略。

或者反过来说，如果对于每个非空节点才添加 () 的话，那么当「有右子树」同时「没有左子树」时，左子树的 () 不能被忽略，需要额外添加，从而确保生成出来的字符串能够与「有左子树」同时「没有右子树」的情况区分开来，而不会产生二义性。

代码

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        public String tree2str(TreeNode root) {
            StringBuilder stringBuilder = new StringBuilder();
            creatStr(root,stringBuilder);
            return stringBuilder.toString();
    
        }
        public void creatStr(TreeNode t,StringBuilder stringBuilder ){
            if(t == null){
                return ;
            }
            stringBuilder.append(t.val);
            //根节点左树有节点就进行拼接
            if(t.left != null){
                stringBuilder.append("(");
                //递归
                creatStr(t.left,stringBuilder);
                stringBuilder.append(")");
            }
            //左为空，但右不为空，需要加（）
            else{
                if(t.right == null){
                    return;
                }
                else{
                    stringBuilder.append("()");
                }
            }
            //判断根节点右树拼接
            if(t.right != null){
                stringBuilder.append("(");
                creatStr(t.right,stringBuilder);
                stringBuilder.append(")");
            }
        }
    }

class Solution {
        
        StringBuilder sb = new StringBuilder();
        public String tree2str(TreeNode root) {
            dfs(root);
            return sb.substring(1, sb.length() - 1);
        }
        void dfs(TreeNode root) {
            sb.append("(");
            sb.append(root.val);
            if(root.left != null){
                dfs(root.left);
            }
            else if(root.right != null){
                sb.append("()");
            }
            if(root.right != null){
                dfs(root.right);
            }
            sb.append(")");     
        }
    }

[ced485cbb11e458d81a746890b32cf3f.gif]: https://img-blog.csdnimg.cn/ced485cbb11e458d81a746890b32cf3f.gif
[Link 1]: https://blog.csdn.net/chenchenchencl?spm=1011.2421.3001.5343
[java]: https://blog.csdn.net/chenchenchencl/category_11932758.html
[Link 2]: https://www.nowcoder.com/link/pc_csdncpt_qdmdlcf_c
[e68c41710339407bad76d70bd931af42.png]: https://img-blog.csdnimg.cn/e68c41710339407bad76d70bd931af42.png
[379dfb619610441cb2623a6f13ca2879.png]: https://img-blog.csdnimg.cn/379dfb619610441cb2623a6f13ca2879.png