二叉树二叉树的所有路径
0x00 题目
给定一个二叉树,返回所有
从根
节点到叶子
节点的路径
0x01 思路
这个问题就像是:
从山顶往山脚走,有很多条路
你需要把所有下山的路都找出来
既然是找线路,就应该习惯性地想到,使用 深度优先
的遍历方式:递归
!
0x02 解法
语言:Swift
树节点:TreeNode
public class TreeNode {
public var val: Int
public 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 = val
self.left = left
self.right = right
}
}
解法一:
可以先把一条路径的所有节点,放在数组内,然后生成路径
func binaryTreePaths(_ root: TreeNode?) -> [String] {
guard let root = root else { return [] }
// 存放所有路径的数组
var res: [String] = []
// 存放当前路径的数组
var tmp: [String] = []
// 递归函数
func build(_ root: TreeNode?) {
// 没路了,返回
if root == nil {
return
}
// 添加节点
tmp.append("\(root!.val)")
// 往下走
build(root?.left)
build(root?.right)
// 叶子节点,走到底了
if root?.left == nil && root?.right == nil {
// 存放结果
res.append(tmp.joined(separator:"->"))
}
// 移除最后一步,回头找另外的路线
tmp.removeLast()
}
// 开始下山啦~
build(root)
return res
}
解法二:
递归的同时生成路径
func binaryTreePaths(_ root: TreeNode?) -> [String] {
guard let root = root else { return [] }
var res: [String] = []
func build(_ root: TreeNode?, _ path: String) {
// 叶子节点,走到底了
if root?.left == nil && root?.right == nil {
// 存放结果
res.append(path)
return
}
// 左边有路,往左边走
if let left = root?.left {
build(left, path "->\(left.val)")
}
// 右边有路,往右边走
if let right = root?.right {
build(right, path "->\(right.val)")
}
}
// 开始下山啦~
build(root, "\(root.val)")
return res
}
小笔记
笔记从未如此简单
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgabaki
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01