20240715题目

589. N 叉树的前序遍历

给定一个 n 叉树的根节点 root ，返回 其节点值的 前序遍历 。

n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔；

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    void solve(Node* root,vector<int> &ans)
    {
        if(!root)return ;
        ans.push_back(root->val);
        for(auto & t : root->children)
            solve(t,ans);
    }
    vector<int> preorder(Node* root) {
        vector<int>ans;
        solve(root,ans);
        return ans;
    }
};

590. N 叉树的后序遍历

给定一个 n 叉树的根节点 root ，返回 其节点值的 后序遍历 。

n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔;

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    void solve(Node* root,vector<int> &ans)
    {
        if(!root)return ;
        for(auto & t : root->children)
            solve(t,ans);
        ans.push_back(root->val);
    }
    vector<int> postorder(Node* root) {
        vector<int>ans;
        solve(root,ans);
        return ans;
    }
};

20. 有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

class Solution {
public:
    bool isValid(string s) {
        map<char,int>m{{'(',1},{'[',2},{'{',3},{')',4},{']',5},{'}',6}};
        stack<int>st;
        bool ans=true;
        for(auto c : s)
        {
            int t=m[c];
            if(t>=1&&t<=3)st.push(t);
            else if(!st.empty()&&t==st.top()+3)st.pop();
            else{
                ans=false;
                break;
            }
        }
        if(!st.empty())ans=false;
        return ans;
    }
};

94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void solve(TreeNode *root,vector<int> &ans)
    {
        if(!root)return;
        if(root->left)solve(root->left,ans);
        ans.push_back(root->val);
        if(root->right)solve(root->right,ans);
    }
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>ans;
        solve(root,ans);
        return ans;
    }
};

115. 不同的子序列

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 10^9 + 7 取模。

class Solution {
public:
    int numDistinct(string s, string t) {
        int n=s.size(),m=t.size();
        s=' '+s,t=' '+t;
        vector<vector<long long> >f(n+1,vector<long long>(m+1));
        for(int i=0; i<=n; i++) f[i][0]=1;

        for(int i=1; i<=n; i++)
        {
            for(int j=1;j<=m;j++)
            {
                f[i][j] = f[i-1][j];
                if(s[i] == t[j]) f[i][j] += f[i-1][j-1];
                f[i][j]%=1000000007;
            }
        }
        return f[n][m];
    }
};