【二叉树】二叉树寻路

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
五笔学习好帮手
微信 搜索即可~

---