【二叉树】根据二叉树创建字符串

0x00 题目

给你一棵二叉树，使用 前序 遍历的方式
将这个它转换成一个由 括号 和 整数 组成的字符串

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

粟子 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)”

和第一个示例相似
但不能省略第一个对括号

0x01 思路

在遍历子树前，添加左括号 (
遍历子树
在遍历子树后，添加右括号 )

这样就能把节点放在括号里面了

左子树为空，右子树不为空时
左括号 不 可以省略，添加判断即可

0x02 解法

语言：Swift

树节点：TreeNode

public class TreeNode {public var val: Intpublic var left: TreeNode?public var right: TreeNode?public init() { self.val = 0; self.left = nil; self.right = nil; }public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {self.val = valself.left = leftself.right = right}
}

方法 一：
把遍历的结果，先放在 数组 里面，最后再生成 字符串

func tree2str(_ t: TreeNode?) -> String {guard let t = t else {return ""}// 存放结果var array = [String]()func dfs(_ t: TreeNode?) {guard let t = t else {return}// 添加当前节点array.append("\(t.val)")// 左子树不为空时if t.left != nil {// 添加左括号array.append("(")// 递归遍历下一个节点dfs(t.left)// 添加右括号array.append(")")}// 右子树不为空时if t.right != nil {// 左子树不为空时，左括号不能省略if t.left == nil {array.append("()")}// 添加左括号array.append("(")// 递归遍历下一个节点dfs(t.right)// 添加右括号array.append(")")}}dfs(t)return array.joined()
}

方法 二：
直接使用一个 字符串，在遍历的同时进行拼接
逻辑跟上面的方法一致，把 数组 的添加变成了 字符串 的拼接

func tree2str(_ t: TreeNode?) -> String {guard let t = t else {return ""}var out = ""func dfs(_ t: TreeNode?) {guard let t = t else {return}out += "\(t.val)"if t.left != nil {out += "("dfs(t.left)out += ")"}if t.right != nil {if t.left == nil {out += "()"}out += "("dfs(t.right)out += ")"}}dfs(t)return out
}

小五笔

86版，98版，二选一
当然，你可以全都要~

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！