• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1104.二叉树寻路|PathInZigzagLabelledBinaryTree

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,...), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,...), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]

Constraints:

  • 1 <= label <= 10^6

在一棵无限的二叉树上,每个节点都有两个子节点,树中的节点 逐行 依次按 “之” 字形进行标记。

如下图所示,在奇数行(即,第一行、第三行、第五行……)中,按从左到右的顺序进行标记;

而偶数行(即,第二行、第四行、第六行……)中,按从右到左的顺序进行标记。

给你树上某一个节点的标号 label,请你返回从根节点到该标号为 label 节点的路径,该路径是由途经的节点标号所组成的。

示例 1:

输入:label = 14
输出:[1,3,4,14]

示例 2:

输入:label = 26
输出:[1,2,6,10,26]

提示:

  • 1 <= label <= 10^6

Runtime: 4 ms
Memory Usage: 20.5 MB
 1 class Solution {
 2     func pathInZigZagTree(_ label: Int) -> [Int] {
 3         var ret:[Int] = [Int]()
 4         var cur:Int = label
 5         while(true)
 6         {
 7             ret.insert(cur,at:0)
 8             if cur == 1 {break}
 9             cur /= 2
10             let h:Int = highestOneBit(cur)
11             cur ^= h-1
12         }
13         return ret
14     }
15     
16     func highestOneBit(_ i:Int) -> Int
17     {
18         var i = i
19         // HD, Figure 3-1
20         i |= (i >>  1)
21         i |= (i >>  2)
22         i |= (i >>  4)
23         i |= (i >>  8)
24         i |= (i >> 16)
25         return i - (i >> 1)
26     }
27 }

8ms 
 1 class Solution {
 2     func pathInZigZagTree(_ label: Int) -> [Int] {
 3         var result = [Int]()
 4         var log = 1
 5         while log <= label {
 6             log <<= 1
 7         }
 8         var label = label 
 9         while label >= 1 {
10             result.append(label)
11             label = log + log / 2 - label - 1
12             label /= 2
13             log /= 2
14         }
15         return result.reversed()
16     }
17 }

316ms

 1 class Solution {
 2     func pathInZigZagTree(_ label: Int) -> [Int] {
 3         var level = 1 
 4         var arr = [Int]()
 5         
 6         outer: while true {
 7             let left = Int(pow(2.0, Double(level-1)))
 8             let right = Int(pow(2.0, Double(level))) - 1
 9 
10             if level % 2 == 1 {
11                 for v in left...right {
12                     if v == label { 
13                         arr.append(v)
14                         break outer
15                     }
16                     arr.append(v)
17                 }
18             } else {
19                 for v in stride(from:right, through: left, by: -1) {
20                     if v == label { 
21                         arr.append(v)
22                         break outer
23                     }
24                     arr.append(v)
25                 }
26             }
27             level += 1
28         }
29         
30         var idx = arr.count - 1
31         var result = [Int]()
32         
33         while idx > 0 {
34             result.append(arr[idx])
35             idx = (idx - 1) / 2
36         }
37         result.append(arr[0])
38         return result.reversed()
39     }
40 }

536ms

 1 class Solution {
 2     func pathInZigZagTree(_ label: Int) -> [Int] {
 3         var tree = [Int]()
 4         var prevPow = 1
 5         var reverse = false
 6         outer: for i in 1...20 {
 7             let num = Int(pow(2, Double(i)))
 8             if reverse {
 9                 for j in stride(from: num - 1, through: prevPow, by: -1) {
10                     tree.append(j)
11                     if j == label { break outer }
12                 }
13             } else {
14                 for j in stride(from: prevPow, to: num, by: 1) {
15                     tree.append(j)
16                     if j == label { break outer }
17                 }
18             }
19             prevPow = num
20             reverse = !reverse
21         }
22         var res = [Int]()
23         var i = tree.count - 1
24         while i > 0 {
25             res.append(tree[i])
26             i = (i - 1)/2
27         }
28         res.append(tree[i])
29         return Array(res.reversed())
30     }
31 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap