Python 中之之字形标记二叉树路径

假设在一个无限二叉树中，每个节点都有两个子节点，节点按行顺序标记。现在在奇数行（第一行、第三行、第五行……），标记是从左到右的，在偶数行（第二行、第四行、第六行……），标记是从右到左的。所以树将是这样的：

所以我们给出了这棵树中一个节点的标签，我们需要找到从树的根节点到该节点的路径上的标签。所以如果输入是 label = 14，那么输出将是 [1,3,4,14]

为了解决这个问题，我们将遵循以下步骤：

  • 定义两个数组 tree 和 res，将 0 和 1 插入到 tree 数组中，设置 odd := 1，current := 1 和 two := 2

  • 如果 label = 1，则返回一个包含单个元素 1 的列表。

  • 创建一个无限循环：

    • 如果 odd 不为零，则

      • max_val := current + two

      • temp := max_val

      • 当 temp > current 时

        • 将 temp 插入到 tree 中

        • 如果 temp = label，则退出循环

        • 将 temp 减 1

      • 如果 tree 的最后一个元素是 label，则退出循环

      • current := max_val

    • 否则

      • temp := two

      • 当 temp 不为零时

        • temp := 1，将 current 加 1，然后将 current 插入到 tree 中

        • 如果 current = label，则退出循环

      • 如果 tree 的最后一个元素是 label，则退出循环

    • temp := temp * 2

    • 如果 odd 不为零，则 odd := false，否则 odd := true

  • index := tree 的长度 – 1

  • 当 index 不为 0 时

    • 将 tree[index] 插入到 res 数组中

    • index := index / 2

  • res := res 的反转列表

  • 返回 res

示例（Python）

让我们看看以下实现，以便更好地理解：

 实时演示

class Solution(object):
   def pathInZigZagTree(self, label):
      tree = []
      res = []
      tree.append(0)
      tree.append(1)
      odd = 1
      current = 1
      two = 2
      if label == 1:
         return [1]
      while True:
         if odd:
            max_val = current + two
            temp = max_val
            while temp>current:
               tree.append(temp)
               if temp == label:
                  break
               temp-=1
            if tree[-1]== label:
               break
            current = max_val
         else:
            temp = two
            while temp:
               temp-=1
               current+=1
               tree.append(current)
            if current == label:
               break
            if tree[-1]== label:
               break
         two*=2
         odd = not odd
      index = len(tree)-1
      while index:
         res.append(tree[index])
         index//=2
      res=res[::-1]
      return res
ob = Solution()
print(ob.pathInZigZagTree(14))

输入

14

输出

[1,3,4,14]

更新于： 2020-04-30

151 次查看

开启你的 职业生涯

通过完成课程获得认证

开始
广告