【每日算法】 二叉树寻路的两种方式 :「模拟」&「数学」

【每日算法】 二叉树寻路的两种方式 :「模拟」&「数学」

题目描述

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

Tag : 「二叉树」、「模拟」、「数学」

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

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

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

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

示例 1：

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

示例 2：

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

提示：

1 <= label <=

模拟

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

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

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

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 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 list = new ArrayList<>(); for (int i : ans) list.add(i); return list; }}

Python 3 代码：

class Solution: def pathInZigZagTree(self, n: int) -> List[int]: # 第 level 层的起始节点值 def getStart(level): return 2 ** (level-1) # 第 level 层的结束节点值 def getEnd(level): return 2**level - 1 # 计算 n 所在层级 level = 1 while getEnd(level) < n: level += 1 ans = [0] * level idx, cur = level - 1, n while idx >= 0: ans[idx] = cur idx -= 1 tot = start = getStart(level) end = getEnd(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 prevStart = getStart(level - 1) while j > 1: prevStart += 1 j -= 1 cur = prevStart else: # 当前层为奇数层，则当前层节点「从左往右」数值递增，相应计算上一层下标也应该「从左往右」 j = 1 for i in range(start, end + 1, 2): if i == cur or i + 1 == cur: break j += 1 prevEnd = getEnd(level - 1) while j > 1: prevEnd -= 1 j -= 1 cur = prevEnd level -= 1 return ans

时间复杂度：确定所在层级复杂度为；构造答案最坏情况下每个节点会被遍历一次，复杂度为空间复杂度：

数学

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

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

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 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 list = new ArrayList<>(); for (int i : ans) list.add(i); return list; }}

Python 3 代码：

class Solution: def pathInZigZagTree(self, n: int) -> List[int]: # 第 level 层的起始节点值 def getStart(level): return 2 ** (level-1) # 第 level 层的结束节点值 def getEnd(level): return 2**level - 1 level = 1 while getEnd(level) < n: level+=1 ans = [0] * level idx, cur = level - 1, n while idx >= 0: ans[idx] = cur idx -= 1 loc = ((1 << (level)) - 1 - cur) >> 1 cur = (1 << (level - 2)) + loc if level >= 2 else loc level -= 1 return ans

时间复杂度：复杂度上界取决于确定所在层级。复杂度为空间复杂度：

最后

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

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

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

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

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。