LeetCode 1104. 二叉树寻路

Categories:

题目描述
思路分析
1. 解法一：从节点回溯到根（推荐）
相似题目

题目描述

✅ 1104. 二叉树寻路

思路分析

解法一：从节点回溯到根（推荐）

核心思路：

计算当前层范围 [2^level, 2^(level+1)-1]。

若为“反向层”，先映射到正常编号，再除以 2 回到父节点。

依次回溯到根，最后反转路径。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示节点编号。

空间复杂度：O(log n)，存储路径。

import java.util.*;

class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        List<Integer> path = new ArrayList<>();
        int level = 0;
        int node = label;
        while ((1 << (level + 1)) <= node) {
            level++;
        }

        while (node >= 1) {
            path.add(node);
            int start = 1 << level;
            int end = (1 << (level + 1)) - 1;
            int normal = (level % 2 == 0) ? node : (start + end - node);
            node = normal / 2;
            level--;
        }

        Collections.reverse(path);
        return path;
    }
}

func pathInZigZagTree(label int) []int {
    level := 0
    for (1 << (level + 1)) <= label {
        level++
    }

    path := []int{}
    node := label
    for node >= 1 {
        path = append(path, node)
        start := 1 << level
        end := (1 << (level + 1)) - 1
        normal := node
        if level%2 == 1 {
            normal = start + end - node
        }
        node = normal / 2
        level--
    }

    for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
        path[i], path[j] = path[j], path[i]
    }
    return path
}

相似题目

题目	难度	考察点
199. 二叉树的右视图	中等	树遍历
102. 二叉树的层序遍历	中等	层序遍历
662. 二叉树最大宽度	中等	位置编号
1104. 二叉树寻路	中等	数学
103. 二叉树的锯齿形层序遍历	中等	层序遍历

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/67484804