<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 1104. 二叉樹尋路 ## 題目地址(1104. 二叉樹尋路) <https://leetcode-cn.com/problems/path-in-zigzag-labelled-binary-tree/> ## 題目描述 ``` <pre class="calibre18">``` 在一棵無限的二叉樹上,每個節點都有兩個子節點,樹中的節點 逐行 依次按 “之” 字形進行標記。 如下圖所示,在奇數行(即,第一行、第三行、第五行……)中,按從左到右的順序進行標記; 而偶數行(即,第二行、第四行、第六行……)中,按從右到左的順序進行標記。 ![](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlu59hpv3j310p0gumxz.jpg) 給你樹上某一個節點的標號 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 難度,代碼也不難寫出。我們繼續考慮之字形。我們不妨先觀察一下,找下規律。 ![](https://img.kancloud.cn/84/8c/848cb9338fe5d79a615bd74a8b0a4231_786x327.jpg) 以上圖最后一行為例,對于 15 節點,之字變換之前對應的應該是 8 節點。14 節點對應的是 9 節點。。。 全部列舉出來是這樣的: ![](https://img.kancloud.cn/b9/1e/b91e079754056c23cd9e656ea24ee870_812x402.jpg) 我們發現之字變換前后的 label 相加是一個定值。 ![](https://img.kancloud.cn/a1/e0/a1e0c2b0b9405550f617dcb715cb57a0_335x301.jpg) 因此實際上只需要求解出每一層的這個定值,然后減去當前值就好了。(注意我們不需要區分偶數行和奇數行) 問題的關鍵轉化為求解這個定值,這個定值其實很好求,因為每一層的最大值和最小值我們很容易求,而最大值和最小值的和正是我們要求的這個數字。 最大值和最小值這么求呢?由滿二叉樹的性質,我們知道每一層的最小值就是`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 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看