Skip to content

Latest commit

 

History

History
155 lines (118 loc) · 4.22 KB

File metadata and controls

155 lines (118 loc) · 4.22 KB
comments difficulty edit_url rating source tags
true
中等
1544
第 143 场周赛 Q2
数学
二叉树

English Version

题目描述

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

如下图所示,在奇数行(即,第一行、第三行、第五行……)中,按从左到右的顺序进行标记;

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

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

 

示例 1:

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

示例 2:

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

 

提示:

  • 1 <= label <= 10^6

解法

方法一:数学

对于一棵完全二叉树,第 $i$ 行的节点个数为 $2^{i-1}$,第 $i$ 行的节点编号范围为 $[2^{i-1}, 2^i - 1]$。而题目中对于奇数行,按从左到右的顺序进行标记,对于偶数行,按从右到左的顺序进行标记。所以对于第 $i$ 行的节点 $label$,它的互补节点编号为 $2^{i-1} + 2^i - 1 - label$。所以节点 $label$ 的实际父节点编号为 $(2^{i-1} + 2^i - 1 - label) / 2$。我们可以通过不断地求互补节点编号和父节点编号,直到到达根节点,即可得到从根节点到节点 $label$ 的路径。

最后,我们需要将路径反转,因为题目要求路径是从根节点到节点 $label$ 的路径。

时间复杂度 $O(\log n)$,其中 $n$ 为节点 $label$ 的编号。忽略答案的空间消耗,空间复杂度 $O(1)$

Python3

class Solution:
    def pathInZigZagTree(self, label: int) -> List[int]:
        x = i = 1
        while (x << 1) <= label:
            x <<= 1
            i += 1
        ans = [0] * i
        while i:
            ans[i - 1] = label
            label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1
            i -= 1
        return ans

Java

class Solution {
    public List<Integer> pathInZigZagTree(int label) {
        int x = 1, i = 1;
        while ((x << 1) <= label) {
            x <<= 1;
            ++i;
        }
        List<Integer> ans = new ArrayList<>();
        for (; i > 0; --i) {
            ans.add(label);
            label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1;
        }
        Collections.reverse(ans);
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> pathInZigZagTree(int label) {
        int x = 1, i = 1;
        while ((x << 1) <= label) {
            x <<= 1;
            ++i;
        }
        vector<int> ans;
        for (; i > 0; --i) {
            ans.push_back(label);
            label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1;
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

Go

func pathInZigZagTree(label int) (ans []int) {
	x, i := 1, 1
	for x<<1 <= label {
		x <<= 1
		i++
	}
	for ; i > 0; i-- {
		ans = append(ans, label)
		label = ((1 << (i - 1)) + (1 << i) - 1 - label) >> 1
	}
	for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 {
		ans[i], ans[j] = ans[j], ans[i]
	}
	return
}