【2023】字节跳动 10 日心动计划——第十关

1. 二叉树中和为某一值的路径

注意细节，路径必须是从根节点到叶子结点。直接用dfs即可。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> pathSum(TreeNode* root, int target) {
        if (!root) return {};
        dfs(root, target);
        return ans;
    }
    
    void dfs(TreeNode* root, int target) {
        if (!root) return;

        path.push_back(root->val);
        target -= root->val;
        if (target == 0 && !root->left && !root->right) {
            ans.push_back(path);
        }

        dfs(root->left, target);
        dfs(root->right, target);
        path.pop_back();
    }
};

2. 平衡二叉树

AVL树的定义是递归的，即一个树是AVL树当且仅当根节点的左右子树都是AVL树且两者高度差不超过1。

class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if (!root) return true;
        bool cond = abs(getHeight(root->left) - getHeight(root->right)) <= 1;
        return isBalanced(root->left) && isBalanced(root->right) && cond;
    }

    int getHeight(TreeNode* root) {
        if (!root) return 0;
        return max(getHeight(root->left), getHeight(root->right)) + 1;
    }
};

3. 实现 Trie (前缀树)

可参考 深度解析Trie（字典树）。

class Trie {
public:
    static constexpr int N = 1e5 + 10;

    int son[N][26], cnt[N], idx;

    /** Initialize your data structure here. */
    Trie(): idx(0) {
        memset(son, 0, sizeof son);
        memset(cnt, 0, sizeof cnt);
    }

    /** Inserts a word into the trie. */
    void insert(string word) {
        int p = 0;
        for (char c: word) {
            if (!son[p][c - 'a']) son[p][c - 'a'] = ++idx;
            p = son[p][c - 'a'];
        }
        cnt[p]++;
    }

    /** Returns if the word is in the trie. */
    bool search(string word) {
        int p = 0;
        for (char c: word) {
            if (!son[p][c - 'a']) return false;
            p = son[p][c - 'a'];
        }
        return cnt[p] > 0;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    bool startsWith(string prefix) {
        int p = 0;
        for (char c: prefix) {
            if (!son[p][c - 'a']) return false;
            p = son[p][c - 'a'];
        }
        return true;
    }
};