当前位置:网站首页>【二叉树】二叉树寻路
【二叉树】二叉树寻路
2022-07-06 22:41:00 【豪冷啊】
0x00 题目
在一棵无限的二叉树上,每个节点都有两个
子节点
树中的节点 逐行
依次按 “之” 字形进行标记
如下图所示
在奇数行
(即,第一行、第三行、第五行……)中,
按从左到右
的顺序进行标记
而偶数行
(即,第二行、第四行、第六行……)中,
按从右到左
的顺序进行标记
给你树上某一个节点
的标号 label
请你返回从根
节点到该标号
为 label
节点的路径
该路径是由途经的节点标号所组成的
粟子:
输入:label = 14
输出:[1,3,4,14]
0x01 思路
二叉树的每层的数量
与高度
相关
第 1 层,2 ^ 0 = 1
,并且以 1 开头
第 2 层,2 ^ 1 = 2
,并且以 2 开头
第 3 层,2 ^ 2 = 4
,并且以 4 开头
二叉树按正常顺序展示时
1
2,3
4,5,6,7
子节点与父节点的关系为p = c / 2
根据这个规律
可以获取到从节点
到根
的路径上的所有节点
进而根据数量
得到当前节点的高度
然后再对需要反转
的层进行处理
根据高度
可以求出一层中
最左
边L
和最右
边R
的值
还有一个当前值C
如何求出C
的对称值V
呢?
因为反转后是对称
的C
比 L
大多少V
就比 R
小多少
所以V = R - (C - L) = L + R - C
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 pathInZigZagTree(_ label: Int) -> [Int] {
var res: [Int] = []
// 获取到根的路径上的所有节点
var val = label
while val != 0 {
res.append(val)
val = val >> 1 // 除以2,相当于右移
}
// 倒序 [14,4,3,1] -> [1,3,4,14]
res = Array(res.reversed())
var count = res.count - 2
while count > 0 {
// 左边节点值
let left = Int(pow(2.0, Float(count)))
// 右边节点值
let right = left + left - 1
// 当前要替换的节点值
var val = res[count]
// 计算替换的值
val = left + right - val
// 替换
res[count] = val
// 往上,跳过一层
count -= 2
}
return res
}
0x03 我的作品
欢迎体验我的作品之一:小五笔小程序-XWubi
五笔学习好帮手微信
搜索即可~
边栏推荐
- Jetson nano configures pytorch deep learning environment / / to be improved
- How does vscade use the built-in browser?
- Markdown编辑器
- STM32F103ZE+SHT30检测环境温度与湿度(IIC模拟时序)
- Markdown editor
- Two methods of chromosome coordinate sequencing
- 关于01背包个人的一些理解
- 【愚公系列】2022年7月 Go教学课程 005-变量
- Meaning of 'n:m' and '1:n' in database design
- JS variable
猜你喜欢
acwing 843. N-queen problem
In depth analysis of kubebuilder
Flex layout and usage
How does vscade use the built-in browser?
A detailed explanation of head pose estimation [collect good articles]
[Yugong series] go teaching course 005 variables in July 2022
Programmers go to work fishing, so play high-end!
System framework of PureMVC
U++ 元数据说明符 学习笔记
DFS and BFS concepts and practices +acwing 842 arranged numbers (DFS) +acwing 844 Maze walking (BFS)
随机推荐
Oracle - views and sequences
Ansible中的inventory主机清单(预祝你我有数不尽的鲜花和浪漫)
5G VoNR+之IMS Data Channel概念
namespace基础介绍
Markdown编辑器
IMS data channel concept of 5g vonr+
深入解析Kubebuilder
当 Knative 遇见 WebAssembly
Mysql database (basic)
Can I specify a path in an attribute to map a property in my class to a child property in my JSON?
How to design API interface and realize unified format return?
STM32 encapsulates the one key configuration function of esp8266: realize the switching between AP mode and sta mode, and the creation of server and client
leetcode 53. Maximum subarray maximum subarray sum (medium)
Introduction to namespace Basics
Acl2022 | decomposed meta learning small sample named entity recognition
【愚公系列】2022年7月 Go教学课程 005-变量
Flex layout and usage
谈谈讲清楚这件事的重要性
U++4 接口 学习笔记
[Android kotlin collaboration] use coroutinecontext to realize the retry logic after a network request fails