当前位置:网站首页>[binary tree] binary tree path finding
[binary tree] binary tree path finding
2022-07-07 05:30:00 【How cold it is】
0x00 subject
On an infinite binary tree , Every node has Two
Child node
Nodes in the tree Line by line
Press... In turn “ And ” Mark with glyph
As shown in the figure below
stay Odd line
( namely , first line 、 The third line 、 The fifth row ……) in ,
Press From left to right
In the order of
and Even number line
( namely , The second line 、 In the fourth row 、 Sixth elements ……) in ,
Press From right to left
In the order of
Give you a tree node
Label of label
Please return from root
Node to this label
by label
The path of the node
The path is composed of passing node labels
Corn seed :
Input :label = 14
Output :[1,3,4,14]
0x01 Ideas
Of each layer of a binary tree Number
And Height
relevant
The first 1 layer ,2 ^ 0 = 1
, And take 1 start
The first 2 layer ,2 ^ 1 = 2
, And take 2 start
The first 3 layer ,2 ^ 2 = 4
, And take 4 start
When the binary tree is displayed in normal order
1
2,3
4,5,6,7
The relationship between the child node and the parent node is p = c / 2
According to this rule
You can get from node
To root
On the path of All nodes
And then according to Number
Get the name of the current node Height
And then to Need to reverse
Layer of
according to Height
You can find the middle of a layer
most Left
edge L
And the most Right
edge R
Value
There is also a current value C
How to find out C
Symmetric value of V
Well ?
Because after the reverse is symmetry
Of C
Than L
How much larger V
Just like R
How much smaller
therefore V = R - (C - L) = L + R - C
0x02 solution
Language :Swift
Tree node :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
}
}
solution :
func pathInZigZagTree(_ label: Int) -> [Int] {
var res: [Int] = []
// Get all nodes on the path to the root
var val = label
while val != 0 {
res.append(val)
val = val >> 1 // Divide 2, It's equivalent to moving right
}
// In reverse order [14,4,3,1] -> [1,3,4,14]
res = Array(res.reversed())
var count = res.count - 2
while count > 0 {
// Left node value
let left = Int(pow(2.0, Float(count)))
// Right node value
let right = left + left - 1
// Current node value to be replaced
var val = res[count]
// Calculate the replacement value
val = left + right - val
// Replace
res[count] = val
// Upward , Skip a layer
count -= 2
}
return res
}
0x03 My work
Welcome to experience one of my works : Small five pen small program -XWubi
Wubi learning is a good helper WeChat
Search ~
边栏推荐
- [JS component] date display.
- Two methods of thread synchronization
- Design, configuration and points for attention of network unicast (one server, multiple clients) simulation using OPNET
- JVM(二十) -- 性能监控与调优(一) -- 概述
- 漏电继电器LLJ-100FS
- Senior programmers must know and master. This article explains in detail the principle of MySQL master-slave synchronization, and recommends collecting
- QT simple layout box model with spring
- App clear data source code tracking
- Life experience of an update statement
- [optimal web page width and its implementation] [recommended collection "
猜你喜欢
1.AVL树:左右旋-bite
Use, configuration and points for attention of network layer protocol (taking QoS as an example) when using OPNET for network simulation
阿里云的神龙架构是怎么工作的 | 科普图解
What changes will PMP certification bring?
照片选择器CollectionView
Leetcode (417) -- Pacific Atlantic current problem
How Alibaba cloud's DPCA architecture works | popular science diagram
Harmonyos fourth training
Use Zhiyun reader to translate statistical genetics books
JHOK-ZBG2漏电继电器
随机推荐
Tencent cloud database public cloud market ranks top 2!
Complete code of C language neural network and its meaning
How can professional people find background music materials when doing we media video clips?
[opencv] image morphological operation opencv marks the positions of different connected domains
If you want to choose some departments to give priority to OKR, how should you choose pilot departments?
Disk monitoring related commands
论文阅读【MM21 Pre-training for Video Understanding Challenge:Video Captioning with Pretraining Techniqu】
做自媒体视频剪辑,专业的人会怎么寻找背景音乐素材?
利用OPNET进行网络仿真时网络层协议(以QoS为例)的使用、配置及注意点
项目经理如何凭借NPDP证书逆袭?看这里
Creation and use of thread pool
做自媒体,有哪些免费下载视频剪辑素材的网站?
K6el-100 leakage relay
Writing process of the first paper
利用OPNET进行网络单播(一服务器多客户端)仿真的设计、配置及注意点
Scheduledexecutorservice timer
实现网页内容可编辑
MySQL数据库学习(7) -- pymysql简单介绍
Record a pressure measurement experience summary
创始人负债10亿,开课吧即将“下课”?