LeetCode解題紀錄 1104. Path In Zigzag Labelled Binary Tree

Path In Zigzag Labelled Binary Tree - LeetCode

題目

給定一個 binary tree，根節點為 1 每個節點的數字是根據由上到下，左到右然後右到左 z 字型增加，給定一個數字 label，要求返回由這個數字節點開始一直到根節點的路徑

觀察

• 從描述可以知道每一層節點編號從 2^(n) ~ (2^n+1)-1
• 每往上一層，節點數會少一半
• 這是個數學計算問題

思路

• 每一層節點數減半，父節點距離該層的開始節點，只有子節點的一半
• 因為是來回遞增，因此父節點的 offset 方向會跟子節點相反，計算子節點的 offset 時是減去該層最小值，父節點則是該層的最大值減去一半的 offset

Trial 1

結果

TC：O(log n)，SC：O(1)