列表

详情

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

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

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

返回字符串 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"。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
/** * 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) { } };

javascript 解法, 执行用时: 84 ms, 内存消耗: 55.2 MB, 提交时间: 2023-10-15 15:20:51 

/**
 * Definition for a rope tree node.
 * class RopeTreeNode {
 *     constructor(len, val, left, right) {
 *         this.len = (len===undefined ? 0 : len);
 *         this.val = (val===undefined ? "" : val);
 *         this.left = (left===undefined ? null : left);
 *         this.right = (right===undefined ? null : right);
 *     }
 * }
 */
/**
 * @param {RopeTreeNode} root
 * @param {number} k
 * @return {character}
 */
var getKthCharacter = function(root, k) {
    const dfs = node => {
        if(!node) return ''
        if(node.len == 0) return node.val 
        return dfs(node.left) + dfs(node.right)  
    } 
    return dfs(root)[k - 1]
};

cpp 解法, 执行用时: 60 ms, 内存消耗: 36.1 MB, 提交时间: 2023-10-15 15:20:32 

/**
 * 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) {
        string s = process(root);
        return s[k - 1];
    }

    string process(RopeTreeNode* root) {
        if (root->len == 0) {
            return root->val;
        }

        string left = "", right = "";
        if (root->left != nullptr) {
            left = process(root->left);
        }
        
        if (root->right != nullptr) {
            right = process(root->right);
        }
        
        return left + right;
    }
};

golang 解法, 执行用时: 404 ms, 内存消耗: 23 MB, 提交时间: 2023-10-15 15:19:48 

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

python3 解法, 执行用时: 80 ms, 内存消耗: 27.2 MB, 提交时间: 2023-10-15 15:19:27 

# 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]
        """
        ans = None 
        def dfs(node, cnt):
            if not node or cnt==k: return cnt 
            if node.len==0:
                for c in node.val:
                    cnt += 1 
                    if cnt==k:
                        nonlocal ans 
                        ans = c 
            elif cnt+node.len<k: 
                cnt += node.len 
            else:
                cnt = dfs(node.left, cnt)
                cnt = dfs(node.right, cnt)
            return cnt 
        cnt = dfs(root, 0)
        return ans

    # 递归
    def getKthCharacter2(self, root: Optional[object], k: int) -> str:
        if root.len==0:
            return root.val[k-1]
        if root.left:
            if root.left.len==0:#字符串了 
                g=len(root.left.val) 
                return root.left.val[k-1] if g>=k else self.getKthCharacter2(root.right,k-g)
            else:#不是字符串 
                if root.left.len>=k:
                    return self.getKthCharacter2(root.left,k)
                else:
                    return self.getKthCharacter2(root.right,k-root.left.len)
        return self.getKthCharacter2(root.right,k)

上一题

© 2024 leetcode.cn