【二叉樹】二叉樹尋路

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