从 Rope 树中提取第 K 个字符

Submission

运行时间: 46 ms

内存: 26.7 MB

# Definition for a rope tree node.
# class RopeTreeNode(object):
#     def __init__(self, len=0, val="", left=None, right=None):
#         self.len = len
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def getKthCharacter(self, root: Optional[object], k: int) -> str:
        """
        :type root: Optional[RopeTreeNode]
        """
        def dfs(node):
            if not node:
                return 0, ""
            
            if node.len == 0:
                return node.len, node.val
            
            left_len, left_val = dfs(node.left)
            
            if k <= left_len:
                return left_len, left_val
            
            right_len, right_val = dfs(node.right)
            return left_len + right_len, left_val + right_val
        
        _, val = dfs(root)
        return val[k - 1]

Explain

题解的思路是使用深度优先搜索（DFS）来遍历Rope树，并在遍历过程中逐步构建字符串。Rope树是一种二叉树，其中每个节点包含一个长度值、一个字符串值和可能的左右子节点。在DFS过程中，首先检查当前节点是否为空，如果为空则返回长度为0和空字符串。接着，如果当前节点的长度为0（意味着它可能是一个叶节点），则直接返回该节点的值。对于非叶节点，先递归处理左子树。如果左子树的长度大于或等于k，说明第k个字符位于左子树中，因此可以返回左子树的结果。如果不是，再递归处理右子树，并将左右子树的结果合并返回。最终，从合并后的结果中取出第k个字符。

时间复杂度: O(n)

空间复杂度: O(n)

# Definition for a rope tree node.
# class RopeTreeNode(object):
#     def __init__(self, len=0, val='', left=None, right=None):
#         self.len = len
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def getKthCharacter(self, root: Optional[object], k: int) -> str:
        """
        :type root: Optional[RopeTreeNode]
        """
        def dfs(node):
            # 如果节点为空，返回长度0和空字符串
            if not node:
                return 0, ''
            
            # 如果节点长度为0，可能是叶节点，直接返回节点值
            if node.len == 0:
                return node.len, node.val
            
            # 递归处理左子树
            left_len, left_val = dfs(node.left)
            
            # 如果k在左子树的范围内，直接返回左子树结果
            if k <= left_len:
                return left_len, left_val
            
            # 否则，递归处理右子树，并合并结果
            right_len, right_val = dfs(node.right)
            return left_len + right_len, left_val + right_val
        
        # 从树的根开始DFS
        _, val = dfs(root)
        # 返回第k个字符
        return val[k - 1]

Explore

`len`属性在RopeTreeNode中代表的是该节点以及其所有子节点组成的字符串的总长度。这样设计使得我们可以快速获取子树中字符串的长度，便于在进行诸如查找子字符串位置等操作时提供效率。

在题解中，如果一个节点的长度为0被视为叶节点，并直接返回其值，这实际上是基于一个假设，即叶节点不会有子节点，其长度自然是0。如果一个非叶节点的长度错误地设置为0，这将导致算法错误地处理这些节点，因为它会忽略其子节点的存在和内容，从而影响最终结果。正确的做法是确保非叶节点的长度应该是其所有子节点字符串长度的总和。

题解中通过首先递归左子树，并检查`k`是否小于或等于`left_len`来确定是否找到所需字符。如果不是，即`k`大于`left_len`，则减去`left_len`并对右子树进行递归，这样可以确保不会遗漏或重复计算字符。具体来说，右子树的递归应该是基于新的索引`k - left_len`，这样可以直接定位到右子树中正确的字符位置。这种方法确保了处理的精确性和效率。