提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【算法千题案例】每日LeetCode打卡——86.根据二叉树创建字符串

算法 递归
2023-03-20 15:00:01 时间

原题样例：根据二叉树创建字符串

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

示例1:

输入: 二叉树: [1,2,3,4]
       1
     /   
    2     3
   /    
  4     

输出: "1(2(4))(3)"

解释: 原本将是“1(2(4)())(3())”，
在你省略所有不必要的空括号对之后，
它将是“1(2(4))(3)”。

示例2:

输入: 二叉树: [1,2,3,null,4]
       1
     /   
    2     3
       
      4 

输出: "1(2()(4))(3)"

解释: 和第一个示例相似，
除了我们不能省略第一个对括号来中断输入和输出之间的一对一映射关系。

提示：

  • 两个列表的长度范围都在 [1, 1000]内。
  • 两个列表中的字符串的长度将在[1，30]的范围内。
  • 下标从0开始，到列表的长度减1。
  • 两个列表都没有重复的元素。

C#方法：递归遍历

递归遍历，遇到空节点的时候使用（）代替

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
           StringBuilder str = new StringBuilder();
        public string Tree2str(TreeNode t)
        {
           
            if (t!=null)
            {
                def(t);
            }
            return str.ToString();
        }
        public void def(TreeNode root)
        {
            if (root==null)
            {
                return;
            }
             str.Append(root.val);
            if (root.left!=null|| root.right != null)
            {
                str.Append('(');
                def(root.left);
                str.Append(')');
            }
            if (root.right != null)
            {
                str.Append('(');
                def(root.right);
                str.Append(')');
            }            
        }

}

执行结果

通过
执行用时：92 ms，在所有 C# 提交中击败了92.50%的用户
内存消耗：40.9 MB，在所有 C# 提交中击败了84.90%的用户

Java 方法：递归

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

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

虑完上面的 4 种情况，我们就可以得到最终的字符串。

代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public 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)+")";   
    }
}

执行结果

通过
执行用时：15 ms，在所有 Java  提交中击败了44.08%的用户
内存消耗：40.1 MB，在所有 Java 提交中击败了24.40%的用户

复杂度分析

时间复杂度：O( n )
空间复杂度：O(n)

总结

  • 今天是力扣算法题打卡的第八十六天！
  • 文章采用 C#和 Java 两种编程语言进行解题
  • 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
  • 那今天的算法题分享到此结束啦，明天再见！

相关文章