【二叉树】二叉树寻路

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 我的作品