二叉树从二叉树节点到另节点每一步的方向
0x00 题目
给你一棵 二叉树 的根节点 root
这棵二叉树总共有 n
个节点
每个节点的值为 1
到 n
中的一个整数
且互不相同
给你一个整数 startValue
表示起点节点 s
的值
和另一个不同的整数 destValue
表示终点节点 t
的值
请找到从节点 s
到节点 t
的 最短
路径
并以字符串的形式返回每一步的方向
每一步用 大写
字母 ‘L’ ,‘R’ 和 ‘U’ 分别表示一种方向:
L
表示从一个节点前往它的 左孩子
节点R
表示从一个节点前往它的 右孩子
节点U
表示从一个节点前往它的 父
节点
请你返回从 s 到 t 最短路径
每一步的方向
0x01 思路
因为有 2
个目标
所以有 2
条路径
先把 2
条路径找出来
然后再找出最近
的公共祖先
最后再拼接路径
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 getDirections(_ root: TreeNode?, _ startValue: Int, _ destValue: Int) -> String {
guard let root = root else { return "" }
// 第一条路径
var path1: [(TreeNode, String)] = []
// 第二条路径
var path2: [(TreeNode, String)] = []
// 结果
var res = ""
// 节点和方向
var arr: [(TreeNode, String)] = []
func dfs(_ root: TreeNode?, _ val: Int, _ type: String) {
guard let root = root else { return }
// 添加
arr.append((root, type))
if root.val == val {
if val == startValue {
path1 = Array(arr)
}else if val == destValue {
path2 = Array(arr)
}
return
}
dfs(root.left, val, "L")
dfs(root.right, val, "R")
// 往回走了,删除最后一个
arr.removeLast()
}
// 查找第一条路径
dfs(root, startValue, "")
arr.removeAll()
// 查找第二条路径
dfs(root, destValue, "")
var idx1 = 0
var idx2 = 0
let idx = min(path1.count, path2.count)
// 去掉路径中相同的前缀
while idx1 < idx && idx2 < idx {
let t1 = path1[idx1]
let t2 = path2[idx2]
if t1.0.val == t2.0.val {
idx1 = 1
idx2 = 1
}else{
break
}
}
// 第一条路径是从下往上走,所以把方向全部调整为 `U`
for _ in idx1..<path1.count {
res = "U"
}
// 拼接第二条路径
for i in idx2..<path2.count {
res = path2[i].1
}
return res
}
0x03 我的小作品
欢迎体验我的作品之一:小五笔 86 版
五笔学习好帮手~App Store
搜索即可~
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhfgkggf
系列文章
更多
同类精品
更多
-
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