Question

2689. 从 Rope 树中提取第 K 个字符

English Version

题目描述

给定一个二叉树的根节点 root 和整数 k。除了左右孩子之外，该树的每个节点还有另外两个属性：一个仅包含小写英文字母（可能为空）的 字符串 node.val 和一个非负整数 node.len。这棵树中有两种类型的节点：

• 叶子节点：这些节点没有子节点，node.len = 0，node.val 是一个 非空 字符串。
• 内部节点：这些节点至少有一个子节点（最多两个子节点），node.len > 0，node.val 是一个 空 字符串。

上述描述的树被称为 Rope 二叉树。现在我们用以下递归方式定义 S[node]：

• 如果 node 是一个叶子节点，则 S[node] = node.val，
• 否则，如果 node 是一个内部节点，则 S[node] = concat(S[node.left], S[node.right])，且 S[node].length = node.len。

返回字符串 S[root] 的第 k 个字符。

注意：如果 s 和 p 是两个字符串，则 concat(s, p) 是将字符串 p 连接到 s 后面的字符串。例如，concat("ab", "zz") = "abzz"。

 

示例 1：

输入：root = [10,4,"abcpoe","g","rta"], k = 6
输出："b"
解释：在下面的图片中，我们在内部节点上放置一个表示 node.len 的整数，在叶子节点上放置一个表示 node.val 的字符串。 你可以看到，S[root] = concat(concat("g", "rta"), "abcpoe") = "grtaabcpoe"。因此，S[root][5]，表示它的第6个字符，等于 "b"。

示例 2：

输入：root = [12,6,6,"abc","efg","hij","klm"], k = 3
输出："c"
解释：在下面的图片中，我们在内部节点上放置一个表示 node.len 的整数，在叶子节点上放置一个表示 node.val 的字符串。 你可以看到，S[root] = concat(concat("abc", "efg"), concat("hij", "klm")) = "abcefghijklm"。因此，S[root][2]，表示它的第3个字符，等于 "c"。

示例 3：

输入：root = ["ropetree"], k = 8
输出："e"
解释：在下面的图片中，我们在内部节点上放置一个表示 node.len 的整数，在叶子节点上放置一个表示 node.val 的字符串。 你可以看到，S[root] = "ropetree"。因此，S[root][7]，表示它的第8个字符，等于 "e"。

 

提示：

• 这棵树的节点数量在区间 [1, 103]
• node.val 仅包含小写英文字母
• 0 <= node.val.length <= 50
• 0 <= node.len <= 104
• 对于叶子节点， node.len = 0 且 node.val 是非空的
• 对于内部节点， node.len > 0 且 node.val 为空
• 1 <= k <= S[root].length

解法

方法一：DFS

我们可以使用深度优先搜索的方法，定义一个函数 $dfs(root)$，表示从根节点开始搜索，返回以 $root$ 为根节点的子树的字符串。那么答案就是 $dfs(root)[k-1]$。

函数 $dfs(root)$ 的执行逻辑如下：

• 如果 $root$ 为空，返回空字符串；
• 如果 $root$ 是叶子节点，返回 $root.val$；
• 否则，返回 $dfs(root.left) + dfs(root.right)$。

时间复杂度 $O(n^2)$，空间复杂度 $O(n)$。其中 $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:
    def dfs(root):
      if root is None:
        return ""
      if root.len == 0:
        return root.val
      return dfs(root.left) + dfs(root.right)

    return dfs(root)[k - 1]

/**
 * Definition for a rope tree node.
 * class RopeTreeNode {
 *   int len;
 *   String val;
 *   RopeTreeNode left;
 *   RopeTreeNode right;
 *   RopeTreeNode() {}
 *   RopeTreeNode(String val) {
 *     this.len = 0;
 *     this.val = val;
 *   }
 *   RopeTreeNode(int len) {
 *     this.len = len;
 *     this.val = "";
 *   }
 *   RopeTreeNode(int len, TreeNode left, TreeNode right) {
 *     this.len = len;
 *     this.val = "";
 *     this.left = left;
 *     this.right = right;
 *   }
 * }
 */
class Solution {
  public char getKthCharacter(RopeTreeNode root, int k) {
    return dfs(root).charAt(k - 1);
  }

  private String dfs(RopeTreeNode root) {
    if (root == null) {
      return "";
    }
    if (root.val.length() > 0) {
      return root.val;
    }
    String left = dfs(root.left);
    String right = dfs(root.right);
    return left + right;
  }
}

/**
 * Definition for a rope tree node.
 * struct RopeTreeNode {
 *   int len;
 *   string val;
 *   RopeTreeNode *left;
 *   RopeTreeNode *right;
 *   RopeTreeNode() : len(0), val(""), left(nullptr), right(nullptr) {}
 *   RopeTreeNode(string s) : len(0), val(std::move(s)), left(nullptr), right(nullptr) {}
 *   RopeTreeNode(int x) : len(x), val(""), left(nullptr), right(nullptr) {}
 *   RopeTreeNode(int x, RopeTreeNode *left, RopeTreeNode *right) : len(x), val(""), left(left), right(right) {}
 * };
 */
class Solution {
public:
  char getKthCharacter(RopeTreeNode* root, int k) {
    function<string(RopeTreeNode * root)> dfs = [&](RopeTreeNode* root) -> string {
      if (root == nullptr) {
        return "";
      }
      if (root->len == 0) {
        return root->val;
      }
      string left = dfs(root->left);
      string right = dfs(root->right);
      return left + right;
    };
    return dfs(root)[k - 1];
  }
};

/**
 * Definition for a rope tree node.
 * type RopeTreeNode struct {
 *    len   int
 *    val   string
 *    left  *RopeTreeNode
 *    right *RopeTreeNode
 * }
 */
func getKthCharacter(root *RopeTreeNode, k int) byte {
  var dfs func(root *RopeTreeNode) string
  dfs = func(root *RopeTreeNode) string {
    if root == nil {
      return ""
    }
    if root.len == 0 {
      return root.val
    }
    left, right := dfs(root.left), dfs(root.right)
    return left + right
  }
  return dfs(root)[k-1]
}