一. 二叉树

1.1 从中序和后序遍历序列构造二叉树

二叉树的中序遍历与先序遍历，以及二叉树的中序遍历和后序遍历可以唯一地确定一颗二叉树

以中序遍历和后序遍历构造为例：

在后序遍历序列中，最后一个结点一定是二叉树的根结点；而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在后序序列中找到对应的左子序列和右子序列。在后序序列中，左子序列的最后一个结点是左子树的根结点，右子序列的最后一个结点是右子树的根结点。如此递归下去，便能唯一地确定这棵二叉树。

void Tree::inPostBuild(const std::vector<int> &in_order, const std::vector<int> &post_order){
    this->tree_nodes.emplace_back(nullptr);
    auto inner = [this](const auto &inner, const std::vector<int> &in_order, const std::vector<int> &post_order) -> TreeNode*{
        if(post_order.size() == 0)
            return nullptr;
        int value_root = post_order[post_order.size() - 1];
        alice::TreeNode *node = new alice::TreeNode(value_root);
        this->tree_nodes.emplace_back(node);
        if(post_order.size() == 1)
            return node;
    
        int mid_index = 0;
        for(; mid_index < in_order.size(); ++mid_index){
            if(in_order[mid_index] == value_root)
                break;
        }

        std::vector<int> in_left(in_order.begin(), in_order.begin() + mid_index);
        std::vector<int> in_right(in_order.begin() + mid_index + 1, in_order.end());
        std::vector<int> post_left(post_order.begin(), post_order.begin() + in_left.size());
        std::vector<int> post_right(post_order.begin() + in_left.size(), post_order.end() - 1);

        node->lchild = inner(inner, in_left, post_left);
        node->rchild = inner(inner, in_right, post_right);
        return node;                                                        
    };  
    this->root = inner(inner, in_order, post_order);                        
    return;                                                                 
} 

1.2 二叉排序树

二叉排序树（又称二叉搜索树）或者是一颗空树，或者是具有下列特性地二叉树： 1、若左子树非空，则左子树上所有结点的值均小于根结点的值 2、若右子树非空，则右子树上所有结点的值均大于根结点的值 3、左、右子树也分别是一棵二叉排序树

根据二叉排序树的定义，左子树结点值 < 根结点值 < 右子树结点值，所以对二叉排序树进行中序遍历，可以得到一个递增的有序序列

给定二叉搜索树（BST）的根结点和一个值。 你需要在BST中找到结点值等于给定值的节点。 返回以该结点为根的子树。 如果结点不存在，则返回 nullptr

非递归算法

void show(const alice::TreeNode *root){
    auto inner = [](const auto &inner, const alice::TreeNode *root, int depth) -> void{
        if(! root){
            printf("%s null\n", std::string(depth, '-').c_str());
            return;
        }
        printf("%s %d\n", std::string(depth, '-').c_str(), root->data);
        inner(inner, root->lchild, 1 + depth);
        inner(inner, root->rchild, 1 + depth);
    };
    inner(inner, root, 1);
    return;
}

const alice::TreeNode *searchBST(const alice::TreeNode *root, int target_value){
    if(! root)
        return nullptr;
    const alice::TreeNode *node = root;
    while(node && node->data != target_value){
        if(node->data > target_value)
            node = node->lchild;
        else
            node = node->rchild;
    }
    return node;
}

递归算法

const alice::TreeNode *searchBST(const alice::TreeNode *root, int target_value){
    if(! root)
        return nullptr;
    if(root->data == target_value)
        return root;
    if(root->data > target_value)
        return searchBST(root->lchild, target_value);
    else
        return searchBST(root->rchild, target_value);
}

1.3 判断二叉排序树

递归算法，采用中序遍历

bool isBST(const alice::TreeNode *root){                                                                                                                
    const alice::TreeNode *pre = nullptr;                                                                                                               
    auto inner = [&pre](const auto &inner, const alice::TreeNode *root) -> bool{                                                                        
        if(! root)                                                                                                                                      
            return true;                                                                                                                                
        bool is_left = inner(inner, root->lchild);
        if(pre && pre->data >= root->data)
            return false;
        pre = root;
        bool is_right = inner(inner, root->rchild);
        return is_left && is_right;
    };
    return inner(inner, root);
}

非递归算法，采用中序遍历

bool isBST(const alice::TreeNode *root){                                                                                                                
    if(! root)                                                                                                                                          
        return true;                                                                                                                                    
    std::stack<const alice::TreeNode *> stack;                                                                                                          
    const alice::TreeNode *pre_node = nullptr;                                                                                                          
    const alice::TreeNode *cur_node = root;
    while(cur_node || ! stack.empty()){
        if(cur_node){
            stack.push(cur_node);
            cur_node = cur_node->lchild;
        }
        else{
            cur_node = stack.top();
            stack.pop();
            if(pre_node && pre_node->data >= cur_node->data)
                return false;
            pre_node = cur_node;
            cur_node = cur_node->rchild;
        }
    }
    return true;
}

1.4 二叉树中序序列的最小绝对值差

递归算法，采用中序遍历

int minDifBST(const alice::TreeNode *root){                                                                                                             
    int result = INT_MAX;
    const alice::TreeNode *pre_node;
    auto inner = [&result, &pre_node](const auto &inner, const alice::TreeNode *root) -> void{
        if(! root)
            return;
        inner(inner, root->lchild);
        if(pre_node)
            result = std::min(result, root->data - pre_node->data);
        pre_node = root;
        inner(inner, root->rchild);
    };
    inner(inner, root);
    return result;
}

作业

实现二叉树中序序列的最小绝对值差的非递归算法