algo-aha

删除只含0值的子树

• https://leetcode.com/problems/binary-tree-pruning/

TreeNode* pruneTree(TreeNode* root) {
    if (!root) return NULL;
    root->left = pruneTree(root->left);
    root->right = pruneTree(root->right);
    if (!root->left && !root->right && root->val == 0) return NULL;
    return root;
}

扩展：bst中删除值为key的节点

将二叉树右转90度

• https://leetcode.com/problems/binary-tree-upside-down/

TreeNode* upsideDownBinaryTree(TreeNode* root) {
    // 已知右节点为叶节点、左节点非空，或右节点为空。
    // 此题要将二叉树右转90度：左节点=>父节点、右节点=>左节点、父节点=>右节点。
    // 假设本函数能处理好左子树，只需考虑父节点、左节点、右节点这三者的关系。
    if (!root || !root->left) return root;
    auto newRoot = upsideDownBinaryTree(root->left);
    // 右转90度
    root->left->left = root->right;
    root->left->right = root;
    // 右节点已知为叶节点
    root->left = root->right = NULL;
    return newRoot;
}

插入一行值v

• https://leetcode.com/problems/add-one-row-to-tree/

TreeNode* addOneRow(TreeNode* root, int v, int d) { // d是1-based
    TreeNode dummy(0);
    dummy.left = root;
    insert(&dummy, 0, v, d);
    return dummy.left;
}

void insert(TreeNode* root, int depth, int v, int d) {
    if (!root) return;
    // 找到d-1层，在其子节点插入
    if (depth < d - 1) {
        insert(root->left, depth + 1, v, d);
        insert(root->right, depth + 1, v, d);
    } else {
        auto ln = new TreeNode(v);
        ln->left = root->left;
        root->left = ln;

        auto rn = new TreeNode(v);
        rn->right = root->right;
        root->right = rn;                
    }
}

删除节点并返回森林

• https://leetcode.com/problems/delete-nodes-and-return-forest/

vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
    unordered_set<int> toDel(begin(to_delete), end(to_delete));
    vector<TreeNode*> ans;
    root = dfs(root, toDel, ans);
    if (root) ans.push_back(root);
    return ans;
}

TreeNode* dfs(TreeNode *root, unordered_set<int> &toDel, vector<TreeNode*> &ans) {
    if (!root) return nullptr;
    root->left = dfs(root->left, toDel, ans);
    root->right = dfs(root->right, toDel, ans);
    if (!toDel.count(root->val)) return root;
    
    if (root->left) ans.push_back(root->left);
    if (root->right) ans.push_back(root->right);
    return nullptr;
}