编程题2：一个二叉链表示的树T如下图所示。要求在附件中完成以下几个功能函数（不允许使用全局变量；不允许修改已经给定的公共代码部分；可以添加自定义的函数；设计递归或者非递归算法均可） 1、输出从根节点到叶子节点的所有路径； 2、删除指定节点及其以它为根的子树； 3、在指定位置插入一个节点； 4、对以上3个功能，请分别先写出算法思想，再完成编程。

由于没有给出具体的代码框架，下面将分别给出每个功能函数的算法思想和代码实现。

1、输出从根节点到叶子节点的所有路径

算法思想：
从根节点开始，进行深度优先搜索，当遇到叶子节点时，输出路径。在搜索的过程中，需要记录下当前路径。

代码实现：

void printPath(TreeNode* root, vector<int>& path) {
    if (!root) return;
    path.push_back(root->val);
    if (!root->left && !root->right) {
        for (int i = 0; i < path.size(); i++) {
            cout << path[i] << " ";
        }
        cout << endl;
    } else {
        printPath(root->left, path);
        printPath(root->right, path);
    }
    path.pop_back();
}

2、删除指定节点及其以它为根的子树

算法思想：
先寻找待删除节点，如果找到了，就将其子树全部删除。如果没有找到，就分别在左右子树中寻找。

代码实现：

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return NULL;
    if (root->val == key) {
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return NULL;
    } else {
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }
}

3、在指定位置插入一个节点

算法思想：
先寻找待插入节点的位置，如果在左子树中找到了，就插入左子树；如果在右子树中找到了，就插入右子树；如果没有找到，就在当前节点的左右子树中选择一个较矮的子树插入（保证树的平衡）。

代码实现：

TreeNode* insertNode(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (root->val == val) return root;
    if (val < root->val) root->left = insertNode(root->left, val);
    else root->right = insertNode(root->right, val);
    int l = getHeight(root->left);
    int r = getHeight(root->right);
    if (abs(l - r) > 1) {
        if (l > r) {
            if (getHeight(root->left->left) >= getHeight(root->left->right)) {
                root = rightRotate(root);
            } else {
                root->left = leftRotate(root->left);
                root = rightRotate(root);
            }
        } else {
            if (getHeight(root->right->right) >= getHeight(root->right->left)) {
                root = leftRotate(root);
            } else {
                root->right = rightRotate(root->right);
                root = leftRotate(root);
            }
        }
    }
    return root;
}

4、完整代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

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

TreeNode* leftRotate(TreeNode* root) {
    TreeNode* newRoot = root->right;
    root->right = newRoot->left;
    newRoot->left = root;
    return newRoot;
}

TreeNode* rightRotate(TreeNode* root) {
    TreeNode* newRoot = root->left;
    root->left = newRoot->right;
    newRoot->right = root;
    return newRoot;
}

void printPath(TreeNode* root, vector<int>& path) {
    if (!root) return;
    path.push_back(root->val);
    if (!root->left && !root->right) {
        for (int i = 0; i < path.size(); i++) {
            cout << path[i] << " ";
        }
        cout << endl;
    } else {
        printPath(root->left, path);
        printPath(root->right, path);
    }
    path.pop_back();
}

TreeNode* deleteNode(TreeNode* root, int key) {
    if (!root) return NULL;
    if (root->val == key) {
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return NULL;
    } else {
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }
}

TreeNode* insertNode(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (root->val == val) return root;
    if (val < root->val) root->left = insertNode(root->left, val);
    else root->right = insertNode(root->right, val);
    int l = getHeight(root->left);
    int r = getHeight(root->right);
    if (abs(l - r) > 1) {
        if (l > r) {
            if (getHeight(root->left->left) >= getHeight(root->left->right)) {
                root = rightRotate(root);
            } else {
                root->left = leftRotate(root->left);
                root = rightRotate(root);
            }
        } else {
            if (getHeight(root->right->right) >= getHeight(root->right->left)) {
                root = leftRotate(root);
            } else {
                root->right = rightRotate(root->right);
                root = leftRotate(root);
            }
        }
    }
    return root;
}

int main() {
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(3);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(9);

    vector<int> path;
    printPath(root, path);

    root = deleteNode(root, 8);
    printPath(root, path);

    root = insertNode(root, 1);
    printPath(root, path);

    return 0;
}