数树数

问题描述

小蓝最近学了二叉树,他想到了一个问题。

给定一个层数为 n 的满二叉树,每个点编号规则如下:

图片[1]-数树数-值得研究

具体来说,二叉树从上向下数第 p 层,从左往右编号分别为: 1,2,3,4…2p−1。

小蓝给你一条从根节点开始的路径,他想知道到达的节点编号是多少。

例如:路径是 right−left,那么到达的节点是 1−2−3 ,最后到了三号点,如下图所示。

图片[2]-数树数-值得研究

输入格式

第一行输入两个整数 n 表示完全二叉树的层数,q 代表询问的路径数量。

接下来 q 行,每行一个字符串 S ,S 只包含字符 { ‘L’,’R’ },’L’ 代表向左,R 代表向右。

输出格式

输出 q 行,每行输出一个整数,代表最后到达的节点编号。

样例输入

3 6
R
L
LL
LR
RL
RR

样例输出

2
1
1
2
3
4

说明

2≤n≤20,1≤q≤103,1≤∣S∣<n。

完全二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为 K ,且节点总数是 2k−1 ,则它就是满二叉树。

运行限制

语言最大运行时间最大运行内存
C++1s256M
C1s256M
Java2s256M
Python33s256M
PyPy33s256M
Go3s256M
JavaScript3s256M


来自: 2.数树数 – 蓝桥云课

我的题解

def search_tree(string):
    """
    根据输入的字符串在搜索树中进行查找,并返回对应的值。

    参数:
    string (str): 一个由'R'和'L'组成的字符串,代表在搜索树中的路径选择。

    返回:
    int: 根据路径在搜索树中找到的节点的值。每遇到'R',结果乘以2;每遇到'L',结果乘以2后再减去1。
    """
    result = 1  # 初始化结果为1
    for i in range(len(string)):  # 遍历字符串中的每个字符
        if string[i] == "R":  # 如果当前字符为'R'
            result *= 2  # 结果乘以2
        elif string[i] == "L":  # 如果当前字符为'L'
            result = result * 2 - 1  # 结果乘以2后再减去1
    return result


n, q = map(int, input().split())  # 读取输入的两个整数:n和q
while q > 0:  # 当还有查询时
    string_1 = input()  # 读取一个查询字符串
    print(search_tree(string_1))  # 调用函数并打印结果
    q -= 1  # 减少剩余查询数量

AI 题解

ChatGLM-Turbo

from  binary_tree  import  TreeNode

class  Solution:
     def  get_node_id(self,  n:  int,  q:  int,  paths:  List[str])  ->  List[int]:
          tree  =  self.build_tree(n)
         return  [self.get_node_id_helper(tree,  paths[i],  0)  for  i  in  range(q)]

     def  build_tree(self,  n:  int)  ->  TreeNode:
         if  n  ==  1:
             return  TreeNode(1)
         root  =  TreeNode(1)
         root.left  =  self.build_tree(n  -  1)
         root.right  =  self.build_tree(n  -  1)
         return  root

     def  get_node_id_helper(self,  node:  TreeNode,  path:  str,  index:  int)  ->  int:
         if  not  node:
             return  -1
         if  index  ==  len(path):
             return  node.val
         if  path[index]  ==  'L':
             return  self.get_node_id_helper(node.left,  path,  index  +  1)
         else:
             return  self.get_node_id_helper(node.right,  path,  index  +  1)


class  TreeNode:
     def  __init__(self,  val=0,  left=None,  right=None):
         self.val  =  val
         self.left  =  left
         self.right  =  right

解题思路:

  1. 首先构建满二叉树,使用递归方法。
  2. 然后定义一个辅助函数get_node_id_helper,用于递归查找节点编号。
  3. 在主函数中,遍历路径字符串,根据路径字符串中的’L’和’R’判断走向,递归查找节点编号。
  4. 最后将查找到的节点编号返回。

测试用例:

def  test():
     solution  =  Solution()
     n  =  3
     q  =  6
     paths  =  [
         "R",
         "L",
         "LL",
         "LR",
         "RL",
         "RR"
     ]
     print(solution.get_node_id(n,  q,  paths))

test()

输出:

[2,  1,  1,  2,  3,  4]

ERNIE-Bot-4.0

这个问题可以通过模拟二叉树的遍历过程来解决。由于这是一个满二叉树,我们知道每一层的节点数都是2的幂次方。我们可以从根节点开始,根据输入的路径向左或向右移动,同时计算出每一步到达的节点编号。

下面是一个Python程序来解决这个问题:

def traverse_binary_tree(n, paths):
    results = []
    for path in paths:
        node_id = 1  # 初始节点编号为1
        for direction in path:
            # 计算下一层的节点数
            next_level_node_count = 2 ** (len(path) + 1)
            
            # 如果方向是向左,则节点编号不变;如果方向是向右,则节点编号加上左子树的节点数
            if direction == 'L':
                pass  # 节点编号不变
            elif direction == 'R':
                node_id += next_level_node_count // 4
            
            # 进入下一层,节点编号乘以2(因为每层节点数都是上一层的两倍)
            node_id *= 2
            
            # 如果当前层的节点数超过了总的节点数,则需要减去多余的节点数
            if node_id >= next_level_node_count // 2:
                node_id -= next_level_node_count // 4
        
        results.append(node_id)
    
    return results

# 读取输入
n, q = map(int, input().split())
paths = []
for _ in range(q):
    paths.append(input())

# 计算结果并输出
results = traverse_binary_tree(n, paths)
for result in results:
    print(result)

注意:上面的程序逻辑有些复杂,而且在实际运行时会得到错误的结果。这是因为在处理节点编号时,我们需要更仔细地考虑每一层的节点数和路径。我会提供一个更简洁且正确的解决方案。

正确的思路是这样的:我们从根节点开始,节点编号为1。对于路径中的每一步,如果向左走,我们将当前节点编号乘以2;如果向右走,我们将当前节点编号乘以2后再加1。这样,我们就可以直接得到最后到达的节点编号。

下面是修正后的Python程序:

def traverse_binary_tree(paths):
    results = []
    for path in paths:
        node_id = 1  # 初始节点编号为1
        for direction in path:
            if direction == 'L':
                node_id = node_id * 2 - 1
            elif direction == 'R':
                node_id = node_id * 2
        results.append(node_id)
    return results

# 读取输入
n, q = map(int, input().split())
paths = []
for _ in range(q):
    paths.append(input())

# 计算结果并输出
results = traverse_binary_tree(paths)
for result in results:
    print(result)

这个程序应该能够正确地解决小蓝的问题。注意,在向左移动时,我们需要将节点编号乘以2然后减1,这是因为在满二叉树中,左子节点的编号总是父节点编号的两倍然后减1。向右移动时,我们只需要将节点编号乘以2,因为右子节点的编号总是父节点编号的两倍。

文心一言 3.5 V2.5.4

为了解决这个问题,我们需要模拟从根节点开始的路径,根据每个步骤的左右选择来确定最后到达的节点编号。我们可以通过迭代地遍历路径字符串,每次根据当前的位置和选择来确定下一步的位置,直到遍历完整个路径字符串。

以下是用Python编写的代码来解决这个问题:

def find_node_number(n, path):
    # 初始化当前节点编号和当前层数
    current_node = 1
    current_level = 1

    # 遍历路径字符串
    for step in path:
        # 根据当前层数和节点编号确定下一步的节点编号
        if step == 'L':
            # 如果是向左,则下一个节点编号是当前节点编号的左孩子
            current_node = current_node * 2 - 1
        else:
            # 如果是向右,则下一个节点编号是当前节点编号的右孩子
            current_node = current_node * 2

        # 更新当前层数
        current_level += 1

        # 如果到达或超过给定的层数,则停止遍历
        if current_level > n:
            break

    return current_node

# 读取输入
n, q = map(int, input().split())
paths = [input() for _ in range(q)]

# 对每个路径计算节点编号并输出结果
for path in paths:
    print(find_node_number(n, path))

在这个代码中,我们定义了一个函数find_node_number,它接收层数n和路径path作为输入,然后模拟遍历路径的过程,并返回最后到达的节点编号。然后,我们读取输入,对每个路径调用这个函数,并打印出返回的节点编号。

你可以复制这段代码到你的Python环境中,然后输入样例数据来验证它的正确性。


存档地址:https://www.yuque.com/worthstudy/study/tvkghkygziyedzgb?singleDoc# 《数树数》

© 版权声明
THE END
喜欢就点赞支持一下吧,如果觉得不错或日后有所需要,可以收藏文章和关注作者哦。
点赞1
评论 抢沙发

请登录后发表评论

    暂无评论内容