# 1104. 二叉樹尋路 ## 題目地址(1104. 二叉樹尋路) <https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/> ## 題目描述 ``` <pre class="calibre18">``` 在一棵無限的二叉樹上，每個節點都有兩個子節點，樹中的節點 逐行 依次按 “之” 字形進行標記。 如下圖所示，在奇數行（即，第一行、第三行、第五行……）中，按從左到右的順序進行標記； 而偶數行（即，第二行、第四行、第六行……）中，按從右到左的順序進行標記。  給你樹上某一個節點的標號 label，請你返回從根節點到該標號為 label 節點的路徑，該路徑是由途經的節點標號所組成的。 示例 1： 輸入：label = 14 輸出：[1,3,4,14] 示例 2： 輸入：label = 26 輸出：[1,2,6,10,26] 提示： 1 <= label <= 10^6 ``` ``` ## 前置知識 - 二叉樹 ## 公司 - 暫無 ## 思路 假如這道題不是之字形，那么就會非常簡單。 我們可以根據子節點的 label 輕松地求出父節點的 label，公示是 label // 2（其中 label 為子節點的 label）。 如果是這樣的話，這道題應該是 easy 難度，代碼也不難寫出。我們繼續考慮之字形。我們不妨先觀察一下，找下規律。  以上圖最后一行為例，對于 15 節點，之字變換之前對應的應該是 8 節點。14 節點對應的是 9 節點。。。 全部列舉出來是這樣的：  我們發現之字變換前后的 label 相加是一個定值。  因此實際上只需要求解出每一層的這個定值，然后減去當前值就好了。（注意我們不需要區分偶數行和奇數行） 問題的關鍵轉化為求解這個定值，這個定值其實很好求，因為每一層的最大值和最小值我們很容易求，而最大值和最小值的和正是我們要求的這個數字。 最大值和最小值這么求呢？由滿二叉樹的性質，我們知道每一層的最小值就是`2 ** (level - 1)`，而最大值是`2 ** level - 1`。 因此我們只要知道 level 即可，level 非常容易求出，具體可以看下面代碼。 ## 關鍵點 - 滿二叉樹的性質： - 最小值是`2 ** (level - 1)`，最大值是`2 ** level - 1`，其中 level 是樹的深度。 - 假如父節點的索引為 i，那么左子節點就是 2\*i， 右邊子節點就是 2\*i + 1。 - 假如子節點的索引是 i，那么父節點的索引就是 i // 2。 - 先思考一般情況（不是之字形）， 然后通過觀察找出規律 ## 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">pathInZigZagTree</span><span class="hljs-params">(self, label: int)</span> -> List[int]:</span> level = <span class="hljs-params">0</span> res = [] <span class="hljs-keyword">while</span> <span class="hljs-params">2</span> ** level - <span class="hljs-params">1</span> < label: level += <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> level > <span class="hljs-params">0</span>: res.insert(<span class="hljs-params">0</span>, label) label = <span class="hljs-params">2</span> ** (level - <span class="hljs-params">1</span>) + <span class="hljs-params">2</span> ** level - <span class="hljs-params">1</span> - label label //= <span class="hljs-params">2</span> level -= <span class="hljs-params">1</span> <span class="hljs-keyword">return</span> res ``` ``` **復雜度分析** - 時間復雜度：由于每次都在頭部插入 res，因此時間復雜度為 O(logLabel)O(log\_Label)O(logLabel)， 一共插入了 O(logLabel)O(log\_Label)O(logLabel) 次， 因此總的時間復雜度為 O(logLabel?logLabel)O(logLabel \* logLabel)O(logLabel?logLabel)。 - 空間復雜度：O(1)O(1)O(1) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。