LC 1104. 二叉树寻路

题目描述

这是 LeetCode 上的 1104. 二叉树寻路 ，难度为中等。

在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点逐行依次按 “之” 字形进行标记。

如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；

而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。

给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。

示例 1：

1
2
3

输入：label = 14

输出：[1,3,4,14]

示例 2：

1
2
3

输入：label = 26

输出：[1,2,6,10,26]

提示：

$1 <= label <= 10^6$

模拟

一个朴素的做法是根据题意进行模拟。

利用从根节点到任意一层都是满二叉树，我们可以先确定 label 所在的层级 level，然后计算出当前层起始节点值（最小值）和结束节点值（最大值）。

再利用「每层节点数量翻倍」&「隔层奇偶性翻转」，寻址出上一层的节点下标（令每层下标均「从左往右」计算，并从 $1$ 开始），直到构造出答案（寻址到根节点）。

Java 代码：

class Solution {
    // 第 level 层的起始节点值
    int getStart(int level) {
        return (int)Math.pow(2, level - 1);
    }
    // 第 level 层的结束节点值
    int getEnd(int level) {
        int a = getStart(level);
        return a + a - 1;
    }
    public List<Integer> pathInZigZagTree(int n) {
        // 计算 n 所在层级
        int level = 1;
        while (getEnd(level) < n) level++;

        int[] ans = new int[level];
        int idx = level - 1, cur = n;
        while (idx >= 0) {
            ans[idx--] = cur;
            int tot = (int)Math.pow(2, level - 1);
            int start = getStart(level), end = getEnd(level);
            if (level % 2 == 0) {
                // 当前层为偶数层，则当前层节点「从右往左」数值递增，相应计算上一层下标也应该「从右往左」
                int j = tot / 2;
                for (int i = start; i <= end; i += 2, j--) {
                    if (i == cur || (i + 1) == cur) break;
                }
                int prevStart = getStart(level - 1);
                while (j-- > 1) prevStart++;
                cur = prevStart;
            } else {
                // 当前层为奇数层，则当前层节点「从左往右」数值递增，相应计算上一层下标也应该「从左往右」
                int j = 1;
                for (int i = start; i <= end; i += 2, j++) {
                    if (i == cur || (i + 1) == cur) break;
                }
                int prevEnd = getEnd(level - 1);
                while (j-- > 1) prevEnd--;
                cur = prevEnd;
            }
            level--;
        }
        List<Integer> list = new ArrayList<>();
        for (int i : ans) list.add(i);
        return list;
    }
}

C++ 代码：

class Solution {
public:
    int getStart(int level) {
        return (int)pow(2, level - 1);
    }
    int getEnd(int level) {
        int a = getStart(level);
        return a + a - 1;
    }
    vector<int> pathInZigZagTree(int n) {
        int level = 1;
        while (getEnd(level) < n) level++;
        vector<int> ans(level);
        int idx = level - 1, cur = n;
        while (idx >= 0) {
            ans[idx--] = cur;
            int tot = (int)pow(2, level - 1);
            int start = getStart(level), end = getEnd(level);
            
            if (level % 2 == 0) {
                int j = tot / 2;
                for (int i = start; i <= end; i += 2, j--) {
                    if (i == cur || (i + 1) == cur) break;
                }
                int prevStart = getStart(level - 1);
                while (j-- > 1) prevStart++;
                cur = prevStart;
            } else {
                int j = 1;
                for (int i = start; i <= end; i += 2, j++) {
                    if (i == cur || (i + 1) == cur) break;
                }
                int prevEnd = getEnd(level - 1);
                while (j-- > 1) prevEnd--;
                cur = prevEnd;
            }
            level--;
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def pathInZigZagTree(self, n: int) -> List[int]:
        def get_start(level):
            return 2 ** (level - 1)
        
        def get_end(level):
            a = get_start(level)
            return a + a - 1
        
        level = 1
        while get_end(level) < n:
            level += 1

        ans = [0] * level
        idx, cur = level - 1, n
        while idx >= 0:
            ans[idx] = cur
            idx -= 1
            tot = 2 ** (level - 1)
            start, end = get_start(level), get_end(level)
            
            if level % 2 == 0:
                j = tot // 2
                for i in range(start, end + 1, 2):
                    if i == cur or (i + 1) == cur:
                        break
                    j -= 1
                prev_start = get_start(level - 1)
                while j > 1:
                    prev_start += 1
                    j -= 1
                cur = prev_start
            else:
                j = 1
                for i in range(start, end + 1, 2):
                    if i == cur or (i + 1) == cur:
                        break
                    j += 1
                prev_end = get_end(level - 1)
                while j > 1:
                    prev_end -= 1
                    j -= 1
                cur = prev_end
            level -= 1
        return ans

时间复杂度：确定 $n$ 所在层级复杂度为 $O(\log{n})$；构造答案最坏情况下每个节点会被遍历一次，复杂度为 $O(n)$
空间复杂度：$O(1)$

数学

上述解法复杂度上界取决于「由当前行节点位置确定上层位置」的线性遍历。

如果二叉树本身不具有奇偶性翻转的话，显然某个节点 $x$ 的父节点为 $\left \lfloor \frac{x}{2} \right \rfloor$，但事实上存在奇偶性翻转，而在解法一中我们已经可以 $O(1)$ 计算某一层的起始值和结束值，有了「起始值 & 结算值」和「当前节点所在层的相对位置」，只需要利用“对称性”找到父节点在上层的相应位置，然后根据相应位置算出父节点值即可。

Java 代码：

class Solution {
    int getStart(int level) {
        return (int)Math.pow(2, level - 1);
    }
    int getEnd(int level) {
        int a = getStart(level);
        return a + a - 1;
    }
    public List<Integer> pathInZigZagTree(int n) {
        int level = 1;
        while (getEnd(level) < n) level++;
        int[] ans = new int[level];
        int idx = level - 1, cur = n;
        while (idx >= 0) {
            ans[idx--] = cur;
            int loc = ((1 << (level)) - 1 - cur) >> 1;
            cur = (1 << (level - 2)) + loc;
            level--;
        }
        List<Integer> list = new ArrayList<>();
        for (int i : ans) list.add(i);
        return list;
    }
}

C++ 代码：

class Solution {
public:
    int getStart(int level) {
        return pow(2, level - 1);
    }
    int getEnd(int level) {
        int a = getStart(level);
        return a + a - 1;
    }
    vector<int> pathInZigZagTree(int n) {
        int level = 1;
        while (getEnd(level) < n) level++;
        vector<int> ans(level);
        int idx = level - 1, cur = n;
        while (idx >= 0) {
            ans[idx--] = cur;
            if (level == 1) break;
            int loc = ((1 << level) - 1 - cur) >> 1;
            cur = (1 << (level-2)) + loc;
            level--;
        }
        return ans;
    }
};

Python 代码：

class Solution:
    def pathInZigZagTree(self, n: int) -> List[int]:
        def get_start(level):
            return 2 ** (level - 1)
        
        def get_end(level):
            a = get_start(level)
            return a + a - 1

        level = 1
        while get_end(level) < n:
            level += 1
        ans = [0] * level
        idx, cur = level - 1, n
        while idx >= 0:
            ans[idx] = cur
            idx -= 1
            if level == 1:
                break
            loc = ((1 << level) - 1 - cur) >> 1
            cur = (1 << (level - 2)) + loc
            level -= 1
        return ans

时间复杂度：复杂度上界取决于确定 $n$ 所在层级。复杂度为 $O(\log{n})$
空间复杂度：$O(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1104 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

模拟数学二叉树

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

LC 1834. 单线程 CPU 上一篇

LC 863. 二叉树中所有距离为 K 的结点下一篇