一. 二叉树

1.1 找树左下角的值

给定一个二叉树，在树的最后一行找到最左边的值

递归算法，采用前序遍历

int bottomLeafValue(const alice::TreeNode *root){                                                                                                       
    if(! root){                                                                                                                                         
        return -1;                                                                                                                                      
        printf("The tree isn's exist.\n");                                                                                                              
    }
    int depth_max = 1;
    int result = root->data;
    auto inner = [&depth_max, &result](const auto &inner, const alice::TreeNode *root, int depth) -> void{
        if(! root->lchild && ! root->rchild){
            if(depth > depth_max){
                depth_max = depth;
                result = root->data;
            }
            return;
        }
        if(root->lchild)
            inner(inner, root->lchild, depth+1);
        if(root->rchild)
            inner(inner, root->rchild, depth+1);
    };
    inner(inner, root, 1);
    return result;
}

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

int bottomLeafValue(const alice::TreeNode *root){
    if(! root){
        return -1;
        printf("The tree isn's exist.\n");
    }
    std::queue<const alice::TreeNode *> queue; 
    queue.push(root);
    int result = 0;
    while(! queue.empty()){
        int queue_size = queue.size();
        for(int i = 0; i < queue_size; ++i){
            const alice::TreeNode *node = queue.front();
            queue.pop();
            if(i == 0)
                result = node->data;
            if(node->lchild)
                queue.push(node->lchild);
            if(node->rchild)
                queue.push(node->rchild);
        }
    } 
    return result;
}

1.2 路径总和

递归算法，采用前序遍历

std::vector<std::string> sumPath(const alice::TreeNode *root, int target_sum){
    std::vector<std::string> all_path;
    if(! root)
        return all_path;
    auto inner = [&all_path, target_sum](const auto &inner, const alice::TreeNode *root, std::vector<int> path, int sum){
        if(! root->lchild && ! root->rchild){
            if(sum == target_sum){
                std::string path_sum;
                for(int i = 0; i < path.size(); ++i){
                    path_sum += std::to_string(path[i]);
                    if(i != path.size()-1)
                        path_sum += " -> ";
                }
                all_path.emplace_back(path_sum);
            }
            return;
        }
        
        if(root->lchild){
            path.emplace_back(root->lchild->data);
            inner(inner, root->lchild, path, sum+root->lchild->data);
            path.pop_back();
        }

        if(root->rchild){
            path.emplace_back(root->rchild->data);
            inner(inner, root->rchild, path, sum+root->rchild->data);
            path.pop_back();
        }
    };
    std::vector<int> path;
    path.emplace_back(root->data);
    inner(inner, root, path, root->data);
    return all_path;
}

非递归算法

template<typename T>
void show(const std::vector<T> &vec){
    std::cout << '{';                                                                                                                                   
    for(int i = 0; i < vec.size(); ++i){
        std::cout << vec[i];
        if(i != vec.size()-1)
            std::cout << ", ";
    }
    std::cout << '}';
}

std::vector<std::string> sumPath(const alice::TreeNode *root, int target_sum){
    std::vector<std::string> all_path;
    if(! root)
        return all_path;
    std::stack<const alice::TreeNode *> stack_node;
    std::stack<std::string> stack_path;
    std::stack<int> stack_sum;
    stack_node.push(root);
    stack_path.push(std::to_string(root->data));
    stack_sum.push(root->data);
    while(! stack_node.empty()){
        const alice::TreeNode *top_node = stack_node.top();
        stack_node.pop();
        std::string top_path = stack_path.top();
        stack_path.pop();
        int top_sum = stack_sum.top();
        stack_sum.pop();
        if(! top_node->lchild && ! top_node->rchild){
            if(top_sum == target_sum)
                all_path.emplace_back(top_path);
            continue;
        }

        if(top_node->rchild){
            stack_node.push(top_node->rchild);
            stack_path.push(top_path + " -> " + std::to_string(top_node->rchild->data));
            stack_sum.push(top_sum + top_node->rchild->data);
        }
        
        if(top_node->lchild){
            stack_node.push(top_node->lchild);
            stack_path.push(top_path + " -> " + std::to_string(top_node->lchild->data));
            stack_sum.push(top_sum + top_node->lchild->data);
        }
    }
    return all_path;
}

1.4 二叉排序树

二叉排序树（又称二叉搜索树）或者是一颗空树，或者是具有下列特性地二叉树：

1、若左子树非空，则左子树上所有结点的值均小于根结点的值

2、若右子树非空，则右子树上所有结点的值均大于根结点的值

3、左、右子树也分别是一棵二叉排序树

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

作业

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