572. Subtree of Another Tree

tags: Easy、Tree

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

解法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSame(struct TreeNode* t1, struct TreeNode* t2) {
    if (t1 == NULL && t2 == NULL) {
        return true;
    }
    else if (t1 == NULL || t2 == NULL || t1->val != t2->val){
        return false;
    }
    return isSame(t1->left, t2->left) && isSame(t1->right, t2->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
    if (!root) {
        return false;
    }
    return isSame(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}

897. Increasing Order Search Tree

tags: Easy、Tree

Given the root of a binary search tree, rearrange the tree in in-order so that the leftmost node in the tree is now the root of the tree, and every node has no left child and only one right child.

解法:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void inorderTrace(struct TreeNode* node, struct TreeNode** last) {
    if (!node) { return;}
    inorderTrace(node->left, last);
    node->left = NULL;
    (*last)->right = node;
    *last = node;
    
    inorderTrace(node->right, last);
}


struct TreeNode* increasingBST(struct TreeNode* root) {
    struct TreeNode* dummy = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    dummy -> right = NULL;
    dummy -> left = NULL;
    struct TreeNode* last = dummy;
    inorderTrace(root, &last);
    struct TreeNode* newRoot = dummy->right;
    
    return newRoot;
}

1945. Sum of Digits of String After Convert

tags: Easy、Tree

You are given a string s consisting of lowercase English letters, and an integer k.
First, convert s into an integer by replacing each letter with its position in the alphabet (i.e., replace 'a' with 1, 'b' with 2, ..., 'z' with 26). Then, transform the integer by replacing it with the sum of its digits. Repeat the transform operation k times in total.
For example, if s = "zbax" and k = 2, then the resulting integer would be 8 by the following operations:
Convert: "zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124
Transform #1: 262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17
Transform #2: 17 ➝ 1 + 7 ➝ 8
Return the resulting integer after performing the operations described above.

解法:

int getLucky(char* s, int k) {
    int sum = 0;
    int diff = 96; //ascii的差
    int i = 0;
    while (s[i]) {
        int temp = s[i] - diff;
        sum += temp / 10 + temp % 10;
        i++;
    }
    while (k > 1) {
        int newSum = 0;
        while (sum > 0) {
            newSum += sum % 10;
            sum /= 10;
        }
        k--;
        sum = newSum;
    }
    return sum;
}