Medium

题目描述

在一个无限二叉树中，每个节点都有两个子节点，节点按行顺序标记。

在奇数行（即第一、三、五行等），标记是从左到右的，而在偶数行（第二、四、六行等），标记是从右到左的。

给定树中一个节点的标签，返回从树根到带有该标签的节点的路径上的标签。

示例 1：

输入：label = 14
输出：[1,3,4,14]

示例 2：

输入：label = 26
输出：[1,2,6,10,26]

约束条件：

  • 1 <= label <= 10^6

提示：

  • 根据当前节点的标签，找出该节点父节点的标签必须是什么。

解题思路

这道题的关键是理解之字形标记的规律，并能够从子节点推导出父节点。

首先分析二叉树的标记规律：

  • 第1层：1个节点，标记为1（从左到右）
  • 第2层：2个节点，标记为3,2（从右到左）
  • 第3层：4个节点，标记为4,5,6,7（从左到右）
  • 第4层：8个节点，标记为15,14,13,12,11,10,9,8（从右到左）

解题思路：

  1. 确定节点层数：通过log2(label)可以确定节点在第几层
  2. 找到父节点位置：在正常二叉树中，节点label的父节点是label/2
  3. 处理之字形标记：由于偶数层是反向标记的，需要进行位置转换
  4. 从下往上构建路径：从给定节点开始，不断找父节点直到根节点

核心算法：

  • 对于偶数层的节点，需要将其转换为对应的正常位置
  • 转换公式：正常位置 = 层的起始值 + 层的结束值 - 当前值
  • 然后按正常二叉树规则找父节点，如果父节点在偶数层，再次转换

时间复杂度为O(log n)，因为需要遍历从叶节点到根节点的路径。

代码实现

class Solution {
public:
    vector<int> pathInZigZagTree(int label) {
        vector<int> result;
        
        while (label != 1) {
            result.push_back(label);
            
            // 找到当前层数
            int level = log2(label) + 1;
            
            // 如果当前层是偶数层（从右到左），需要转换为正常位置
            if (level % 2 == 0) {
                int levelStart = 1 << (level - 1);
                int levelEnd = (1 << level) - 1;
                label = levelStart + levelEnd - label;
            }
            
            // 找父节点
            label = label / 2;
            
            // 如果父节点在偶数层，需要转换为之字形位置
            int parentLevel = level - 1;
            if (parentLevel % 2 == 0) {
                int levelStart = 1 << (parentLevel - 1);
                int levelEnd = (1 << parentLevel) - 1;
                label = levelStart + levelEnd - label;
            }
        }
        
        result.push_back(1);
        reverse(result.begin(), result.end());
        return result;
    }
};

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        result = []
        
        while label != 1:
            result.append(label)
            
            # 找到当前层数
            level = label.bit_length()
            
            # 如果当前层是偶数层（从右到左），需要转换为正常位置
            if level % 2 == 0:
                level_start = 1 << (level - 1)
                level_end = (1 << level) - 1
                label = level_start + level_end - label
            
            # 找父节点
            label = label // 2
            
            # 如果父节点在偶数层，需要转换为之字形位置
            parent_level = level - 1
            if parent_level % 2 == 0:
                level_start = 1 << (parent_level - 1)
                level_end = (1 << parent_level) - 1
                label = level_start + level_end - label
        
        result.append(1)
        return result[::-1]

public class Solution {
    public IList<int> PathInZigZagTree(int label) {
        List<int> result = new List<int>();
        
        while (label != 1) {
            result.Add(label);
            
            // 找到当前层数
            int level = (int)Math.Log2(label) + 1;
            
            // 如果当前层是偶数层（从右到左），需要转换为正常位置
            if (level % 2 == 0) {
                int levelStart = 1 << (level - 1);
                int levelEnd = (1 << level) - 1;
                label = levelStart + levelEnd - label;
            }
            
            // 找父节点
            label = label / 2;
            
            // 如果父节点在偶数层，需要转换为之字形位置
            int parentLevel = level - 1;
            if (parentLevel % 2 == 0) {
                int levelStart = 1 << (parentLevel - 1);
                int levelEnd = (1 << parentLevel) - 1;
                label = levelStart + levelEnd - label;
            }
        }
        
        result.Add(1);
        for (int i = 0; i < result.Count / 2; i++) {
            int temp = result[i];
            result[i] = result[result.Count - 1 - i];
            result[result.Count - 1 - i] = temp;
        }
        
        return result;
    }
}

var pathInZigZagTree = function(label) {
    const path = [];
    
    while (label >= 1) {
        path.unshift(label);
        
        // Find the level of current label
        let level = Math.floor(Math.log2(label));
        
        // Find the start and end of current level
        let levelStart = Math.pow(2, level);
        let levelEnd = Math.pow(2, level + 1) - 1;
        
        // Convert to the position as if it were in normal binary tree
        let normalPos;
        if (level % 2 === 0) {
            // Odd row (1-indexed), normal order
            normalPos = label;
        } else {
            // Even row (1-indexed), reversed order
            normalPos = levelStart + levelEnd - label;
        }
        
        // Find parent in normal binary tree
        let parentNormal = Math.floor(normalPos / 2);
        
        // Convert parent back to zigzag position
        let parentLevel = level - 1;
        if (parentLevel >= 0) {
            let parentLevelStart = Math.pow(2, parentLevel);
            let parentLevelEnd = Math.pow(2, parentLevel + 1) - 1;
            
            if (parentLevel % 2 === 0) {
                // Odd row, normal order
                label = parentNormal;
            } else {
                // Even row, reversed order
                label = parentLevelStart + parentLevelEnd - parentNormal;
            }
        } else {
            break;
        }
    }
    
    return path;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)需要从给定节点遍历到根节点，路径长度为O(log n)
空间复杂度O(log n)存储路径所需的额外空间

相关题目