Code – 第255页

LeetCode 242. Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

class Solution {
public:
    bool isAnagram(string s, string t) {
        int a[26] = {0};
        if(s.length() != t.length())
            return 0;
        for(int i = 0; i < s.length(); i++) {
            a[s[i] - 'a']++;
        }
        for(int i = 0; i < t.length(); i++) {
            a[t[i] -'a']--;
        }
        for(int i = 0; i < 26; i++) {
            if(a[i] != 0) {
                return 0;
            }
        }
        return 1;
    }
};

class Solution {

public:

bool isAnagram(string s, string t) {

int a[26] = {0};

if(s.length() != t.length())

return 0;

for(int i = 0; i < s.length(); i++) {

a[s[i] - 'a']++;

}

for(int i = 0; i < t.length(); i++) {

a[t[i] -'a']--;

}

for(int i = 0; i < 26; i++) {

if(a[i] != 0) {

return 0;

}

return 1;

}

};

LeetCode 100. Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p != NULL && q != NULL)
            return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
        return p == NULL && q == NULL;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

bool isSameTree(TreeNode* p, TreeNode* q) {

if(p != NULL && q != NULL)

return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);

return p == NULL && q == NULL;

}

};

LeetCode 237. Delete Node in a Linked List

237. Delete Node in a Linked List
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

分析：因为删除结点本来的步骤是找到当前结点的前一个结点，然后修改前一个结点的 next 指针指向。现在只知道当前要删除的结点，而不知道要删除结点的前一个结点，所以可以通过修改当前要删除结点的值，然后将当前结点指针指向 next 的 next （也就是变成了把后一个结点的值赋给当前结点，然后删除要删除结点的下一个结点），达到删除结点的目的～

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

class Solution {

public:

void deleteNode(ListNode* node) {

node->val = node->next->val;

node->next = node->next->next;

}

};

LeetCode 226. Invert Binary Tree

Invert a binary tree.

4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        TreeNode* p = root;
        if(root == NULL) {
            return NULL;
        }
        
        TreeNode* temp = root->left;
        root->left = root->right;
        root->right = temp;
        
        invertTree(root->left);
        invertTree(root->right);
        
        return p;
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

TreeNode* invertTree(TreeNode* root) {

TreeNode* p = root;

if(root == NULL) {

return NULL;

}

TreeNode* temp = root->left;

root->left = root->right;

root->right = temp;

invertTree(root->left);

invertTree(root->right);

return p;

}

};

LeetCode 111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        else if(root->left == NULL && root->right == NULL)
            return 1;
        else if(root->left == NULL && root->right != NULL)
            return minDepth(root->right) + 1;
        else if(root->right == NULL && root->left != NULL)
            return minDepth(root->left) + 1;
        else {
            int leftdepth = minDepth(root->left);
            int rightdepth = minDepth(root->right);
            return leftdepth < rightdepth ? leftdepth + 1 : rightdepth + 1;
        }
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

int minDepth(TreeNode* root) {

if(root == NULL)

return 0;

else if(root->left == NULL && root->right == NULL)

return 1;

else if(root->left == NULL && root->right != NULL)

return minDepth(root->right) + 1;

else if(root->right == NULL && root->left != NULL)

return minDepth(root->left) + 1;

else {

int leftdepth = minDepth(root->left);

int rightdepth = minDepth(root->right);

return leftdepth < rightdepth ? leftdepth + 1 : rightdepth + 1;

}

};

LeetCode 104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root == NULL)
            return 0;
        if(root->left == NULL && root->right == NULL)
            return 1;
        if(root->left != NULL && root->right == NULL)
            return maxDepth(root->left) + 1;
        if(root->right != NULL && root->left == NULL)
            return maxDepth(root->right) + 1;
        if(root->right != NULL && root->left != NULL) {
            int leftdepth = maxDepth(root->left);
            int rightdepth = maxDepth(root->right);
            return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;
        }
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

int maxDepth(TreeNode* root) {

if(root == NULL)

return 0;

if(root->left == NULL && root->right == NULL)

return 1;

if(root->left != NULL && root->right == NULL)

return maxDepth(root->left) + 1;

if(root->right != NULL && root->left == NULL)

return maxDepth(root->right) + 1;

if(root->right != NULL && root->left != NULL) {

int leftdepth = maxDepth(root->left);

int rightdepth = maxDepth(root->right);

return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;

}

};