头像

tr


访客:5468

离线:1个月前



tr
2个月前
class Solution {
public:
    void connect(TreeLinkNode *root) {
        while (root)
        {
            TreeLinkNode *dummy = new TreeLinkNode(0);
            TreeLinkNode *tail = dummy;
            while (root)
            {
                if (root->left)
                {
                    tail->next = root->left;
                    tail = tail->next;
                }
                if (root->right)
                {
                    tail->next = root->right;
                    tail = tail->next;
                }
                root = root->next;
            }
            tail->next = 0;
            root = dummy->next;
        }
    }
};


活动打卡代码 LeetCode 87. Scramble String

tr
2个月前

(暴力搜索) O(5^n)
递归判断两个字符串是否可以相互转化。

首先判断两个字符串的字符集合是否相同,如果不同,则两个字符串一定不可以相互转化。
然后枚举第一个字符串左半部分的长度,分别递归判断两种可能的情况:

该节点不发生翻转,则分别判断两个字符串的左右两部分是否分别可以相互转化;
该节点发生翻转,则分别判断第一个字符串的左边是否可以和第二个字符串的右边相互转化,且第一个字符串的右边可以和第二个字符串的左边相互转化;

class Solution {
public:
    bool isScramble(string s1, string s2) {
        if (s1 == s2) return true;
        string ss1 = s1, ss2 = s2;
        sort(ss1.begin(), ss1.end()), sort(ss2.begin(), ss2.end());
        if (ss1 != ss2) return false;
        for (int i = 1; i < s1.size(); i ++ )
        {
            if (isScramble(s1.substr(0, i), s2.substr(0, i))
                    && isScramble(s1.substr(i), s2.substr(i)))
                return true;
            if (isScramble(s1.substr(0, i), s2.substr(s2.size() - i))
                    && isScramble(s1.substr(i), s2.substr(0, s2.size() - i)))
                return true;
        }
        return false;
    }
};

作者:yxc
链接:https://www.acwing.com/solution/LeetCode/content/170/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。



tr
2个月前
class Solution {
public:
    long long mx = INT_MIN;
    int solve(TreeNode* root) {
        if(root == NULL)
            return 0;
        int left = max(0, solve(root->left));
        int right = max(0, solve(root->right));

        mx = max(mx, (long long)root->val + left + right);
        return root->val + max(left, right);
    }
    int maxPathSum(TreeNode* root) {
        solve(root);
        return mx;
    }
};



tr
2个月前
class Solution {
public:
    long long mx = INT_MIN;
    int solve(TreeNode* root) {
        if(root == NULL)
            return 0;
        int left = max(0, solve(root->left));
        int right = max(0, solve(root->right));

        mx = max(mx, (long long)root->val + left + right);
        return root->val + max(left, right);
    }
    int maxPathSum(TreeNode* root) {
        solve(root);
        return mx;
    }
};



tr
2个月前
class Solution {
public:
    int ans;
    int diameterOfBinaryTree(TreeNode* root) {
        ans = 0;
        depth(root);
        return max(ans - 1, 0);
    }
    int depth(TreeNode* u)
    {
        if(!u) return 0;
        int l = depth(u->left);
        int r = depth(u->right);
        ans = max(ans, l + r + 1);
        return max(l, r) + 1;
    }
};



tr
2个月前
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return NULL;
        if(root == p || root == q) return root;
        auto l = lowestCommonAncestor(root->left, p, q);
        auto r = lowestCommonAncestor(root->right, p, q);
        if(l && r) return root;
        if(l) return l;
        return r;
    }
};



tr
2个月前
/**
 * 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:

    void inorder_traversal(TreeNode* node, vector<int>& nums)
    {
        if (node == nullptr)
            return;

        inorder_traversal(node->left, nums);
        nums.push_back(node->val);
        inorder_traversal(node->right, nums);
    }


    bool findTarget(TreeNode* root, int k) {

        vector<int> nums;
        inorder_traversal(root, nums);

        int left = 0;
        int right = nums.size() - 1;

        while (left < right)
        {
            int sum = nums.at(left) + nums.at(right);
            if (sum == k)
            {
                return true;
            }
            else if (sum > k)
            {
                --right;
            }
            else
            {
                ++left;
            }
        }

        return false;
    }
};



tr
2个月前
/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if(!root) return ret;
        queue<TreeNode*> q;
        q.push(root);
        while(q.size())
        {
            int len = q.size();
            vector<int> tmp;
            while(len--)
            {
                auto t = q.front(); q.pop();
                tmp.push_back(t->val);
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
            ret.push_back(tmp);
        }
        return ret;
    }
};



tr
2个月前
class Solution {
public:
    string str;
    int index = 0;
    string next()
    {
        if(index >= str.length())
            return "*";
        int p = index;
        while(p < str.length() && str[p] != ',')
            p++;
        int tmp = index;
        index = p + 1;
        return str.substr(tmp, index - tmp - 1);
    }
    bool valid()
    {
        string val = next();
        if(val == "#")
            return true;
        if(val == "*")
            return false;
        return valid() && valid();
    }
    bool isValidSerialization(string preorder) {
        str = preorder;
        return valid() && index >= str.length();
    }
};



tr
2个月前
/**
 * 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:
    unordered_map<int, int> in_index;
    int pre_index = 0;
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int in_st, int in_end)
    {
        if(in_st == in_end)
            return NULL;

        int root_val = preorder[pre_index++];
        int index = in_index[root_val];

        TreeNode* root = new TreeNode(root_val);


        root->left = build(preorder, inorder, in_st, index);
        root->right = build(preorder, inorder, index + 1, in_end);

        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        for(int i = 0; i < inorder.size(); i++) {
            in_index[inorder[i]] = i;
        }
        return build(preorder, inorder, 0, inorder.size());
    }
};