二叉树

1.1 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。输入数据保证，新值和原始二叉搜索树中的任意结点值都不同。

递归算法

void Tree::insertBST(int value){
    auto inner = [this, value](const auto &inner, TreeNode *root) -> TreeNode*{
        if(! root){
            TreeNode *node = new TreeNode(value);
            if(! this->root){
                this->tree_nodes.emplace_back(nullptr);
                this->root = node;
            }
            this->tree_nodes.emplace_back(node);
            return node;
        }
        if(root->data > value)
            root->lchild = inner(inner, root->lchild);
        else
            root->rchild = inner(inner, root->rchild);
        return root;
    };
    inner(inner, this->root);
}

非递归算法

void Tree::insertBST(int value){
    if(! this->root){
        TreeNode *node = new TreeNode(value);
        this->tree_nodes.emplace_back(nullptr);
        this->tree_nodes.emplace_back(node);
        this->root = node;
        return;
    }
    TreeNode *cur_node = this->root;
    TreeNode *pre_node = this->root;
    while(cur_node){
        pre_node = cur_node;
        if(cur_node->data > value)
            cur_node = cur_node->lchild;
        else
            cur_node = cur_node->rchild;
    }
    TreeNode *node = new TreeNode(value);
    this->tree_nodes.emplace_back(node);
    if(pre_node->data > value)
        pre_node->lchild = node;
    else
        pre_node->rchild = node;
}

1.2 二叉搜索树中的删除操作

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变.

删除操作包含以下 5 种情况：

1. 没找到删除的节点，遍历到空节点直接返回了找到删除的节点

2. 左右孩子都为空（叶子节点），直接删除节点， 返回 nullptr 为根节点

3. 删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点

4. 删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点

5. 左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

void Tree::deleteBST(int value){
    auto inner = [](const auto &inner, TreeNode *root, int value) -> TreeNode*{
        if(! root)
            return root;
        if(root->data == value){
            if(! root->lchild && ! root->rchild){
                return nullptr;    
            }
            else if(! root->lchild){
                TreeNode *right = root->rchild;
                return right;
            }
            else if(! root->rchild){
                TreeNode *left = root->lchild;
                return left;
            }
            else{
                TreeNode *find = root->rchild;
                while(find->lchild)
                    find = find->lchild;
                find->lchild = root->lchild;
                root = root->rchild;
                return root;
            }
        }
        else if(root->data > value)
            root->lchild = inner(inner, root->lchild, value);
        else
            root->rchild = inner(inner, root->rchild, value);
        return root;
    };
    inner(inner, this->root, value);
}   

1.3 修剪二叉搜索树

给定一个二叉树，同时给定最小边界 L 和最大边界 R。通过修剪二叉搜索树，使得所有结点的值在【L，R】中（R>=L）。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

递归算法

void Tree::trimBST(int low, int high){
    auto inner = [low, high](const auto &inner, TreeNode *root) -> TreeNode* {
        if(! root)
            return root;
        if(root->data < low){
            TreeNode *right = inner(inner, root->rchild);
            return right;
        }
        if(root->data > high){
            TreeNode *left = inner(inner, root->lchild);
            return left;
        }
        root->lchild = inner(inner, root->lchild);
        root->rchild = inner(inner, root->rchild);
        return root;
    };
    inner(inner, this->root);
}

1.4 将有序数组转换为二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡的二叉搜索树，平衡二叉树是指二叉树的每个节点的左右两个子树的高度差的绝对值不超过 1

递归算法

void Tree::sortToBST(const std::vector<int> &vec){
    if(vec.size() == 0)
        return;
    this->tree_nodes.emplace_back(nullptr);
    auto inner = [&vec, this](const auto &inner, int left, int right) -> TreeNode* {
        if(left > right)
            return nullptr;
        int mid = left + ((right - left) / 2);
        TreeNode *root = new TreeNode(vec[mid]);
        this->tree_nodes.emplace_back(root);
        root->lchild = inner(inner, left, mid-1);
        root->rchild = inner(inner, mid+1, right);
        return root;
    };
    this->root = inner(inner, 0, vec.size()-1);
}

非递归算法，可以使用 3 个队列来模拟，一个队列放遍历的节点，一个队列放左区间下标，一个队列放右区间下标

void Tree::sortToBST(const std::vector<int> &vec){
    if(vec.size() == 0)
        return;
    this->tree_nodes.emplace_back(nullptr);
    this->root = new TreeNode(0);
    this->tree_nodes.emplace_back(this->root);
    std::queue<TreeNode *> queue_node;
    std::queue<int> queue_left;
    std::queue<int> queue_right;
    queue_node.push(this->root);
    queue_left.push(0);
    queue_right.push(vec.size()-1);

    while(! queue_node.empty()){
        TreeNode *cur_node = queue_node.front();
        queue_node.pop();
        int left = queue_left.front();
        queue_left.pop();
        int right = queue_right.front();
        queue_right.pop();
        int mid = left + ((right - left) / 2);

        cur_node->data = vec[mid];
        if(left <= mid - 1){
            cur_node->lchild = new TreeNode(0);
            this->tree_nodes.emplace_back(cur_node->lchild);
            queue_node.push(cur_node->lchild);
            queue_left.push(left);
            queue_right.push(mid-1);
        }
        if(right >= mid + 1){
            cur_node->rchild = new TreeNode(0);
            this->tree_nodes.emplace_back(cur_node->rchild);
            queue_node.push(cur_node->rchild);
            queue_left.push(mid+1);
            queue_right.push(right);
        }
    }
    return;
}

1.5 把二叉搜索树转换为累加树

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树，使每个节点 node 的新值等于原树中大于等于 node 的值之和。

递归算法

void BSTToAccum(alice::TreeNode *root){
    if(! root)
        return;
    int pre = 0;
    auto inner = [&pre](const auto &inner, alice::TreeNode *root) -> void {
        if(root->rchild)
            inner(inner, root->rchild);
        root->data += pre;
        pre = root->data;
        if(root->lchild)
            inner(inner, root->lchild);
    };
    inner(inner, root);
    return;
}

非递归算法

void BSTToAccum(alice::TreeNode *root){
    if(! root)
        return;
    std::stack<alice::TreeNode *> stack;
    alice::TreeNode *cur_node = root;
    int pre = 0;
    while(cur_node || stack.size() != 0){
        if(cur_node){
            stack.push(cur_node);
            cur_node = cur_node->rchild;
        }
        else{
            cur_node = stack.top();
            stack.pop();
            cur_node->data += pre;
            pre = cur_node->data;
            cur_node = cur_node->lchild;
        }
    }
    return;
}