一. 二叉树

1.1 二叉树的最大深度

递归算法，使用前序遍历

int maxDepth(alice::TreeNode *root){
    if(root == nullptr)
        return 0;
    int result = 1;
    auto inner = [&result](const auto &inner, alice::TreeNode *root, int depth) -> void{
        result = result > depth ? result : depth;
        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 maxDepth(alice::TreeNode *root){
    if(root == nullptr)
        return 0;
    int max_left = maxDepth(root->lchild);
    int max_right = maxDepth(root->rchild);
    int result = 1 + std::max(max_left, max_right);
    return result;
}

非递归算法，使用层序遍历是最合适的，因为二叉树最大的深度就是二叉树的层数

int maxDepth(alice::TreeNode *root){
    if(root == nullptr)
        return 0;
    int depth = 0;
    std::queue<alice::TreeNode *> queue;
    queue.push(root);
    while(! queue.empty()){
        ++depth;
        int queue_size = queue.size();
        for(int i = 0; i < queue_size; ++i){
            alice::TreeNode *node = queue.front();
            queue.pop();
            if(node->lchild)
                queue.push(node->lchild);
            if(node->rchild)
                queue.push(node->rchild);
        }
    }
    return depth;
}

1.2 二叉树的最小深度

递归算法，使用前序遍历

int minDepth(const alice::TreeNode *root){
    if(root == nullptr)
        return 0;
    int result = INT_MAX;
    auto inner = [&result](const auto &inner, const alice::TreeNode *root, int depth) -> void{
        if(! root->lchild && ! root->rchild && result > depth)
            result = depth;
        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 minDepth(const alice::TreeNode *root){
    if(root == nullptr)
        return 0;
    int result = 1;
    std::queue<const alice::TreeNode *> queue;
    queue.push(root);
    while(! queue.empty()){
        int queue_size = queue.size();
        for(int i = 0; i < queue_size; ++i){
            const alice::TreeNode *front_node = queue.front();
            queue.pop();
            if(! front_node->lchild && ! front_node->rchild)
                return result;
            if(front_node->lchild)
                queue.push(front_node->lchild);
            if(front_node->rchild)
                queue.push(front_node->rchild);
            ++result;
        }
    }
    return result;
}

1.3 完全二叉树的结点个数

递归算法，采用后序遍历

int nodeNum(const alice::TreeNode *root){                                                                                                               
    if(root == nullptr)                                                                                                                                 
        return 0;
    int left_num = nodeNum(root->lchild);
    int rigth_num = nodeNum(root->rchild);
    int result = 1 + left_num + rigth_num;
    return result;
}

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

int nodeNum(const alice::TreeNode *root){
    if(root == nullptr)
        return 0;
    int result = 0;
    std::queue<const alice::TreeNode *> queue;
    queue.push(root);
    while(! queue.empty()){
        int queue_size = queue.size();
        for(int i = 0; i < queue_size; ++i){
            const alice::TreeNode *front_node = queue.front();
            queue.pop();
            ++result;
            if(front_node->lchild)
                queue.push(front_node->lchild);
            if(front_node->rchild)
                queue.push(front_node->rchild);
        }
    }
    return result;
}

1.4 平衡二叉树

二叉树中任意结点的左、右子树高度差的绝对值不超过 1

bool isAVL(const alice::TreeNode *root){
    if(root == nullptr)
        return true;
    auto inner = [](const auto &inner, const alice::TreeNode *root) -> int{
        if(root == nullptr)
            return 0;
        int left_h = inner(inner, root->lchild);
        if(left_h == -1)
            return -1;
        int right_h = inner(inner, root->rchild);
        if(right_h == -1)
            return -1;
        if(std::abs(left_h - right_h) > 1)
            return -1;
        else
            return 1 + std::max(left_h, right_h);
    };
    return inner(inner, root) == -1 ? false : true;
}

1.5 二叉树的所有路径

递归算法, 使用前序遍历

template <typename T>
void showVec(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> allPath(const alice::TreeNode *root){
    std::vector<std::string> all_path;
    if(root == nullptr)
        return all_path;
    auto inner = [&all_path](const auto &inner, const alice::TreeNode *root, std::vector<int> &path) -> void{
        if(! root->lchild && ! root->rchild){
            std::string str;
            for(int i = 0; i < path.size(); ++i){
                str += std::to_string(path[i]);
                if(i != path.size() - 1)
                    str += " -> ";
            }
            all_path.emplace_back(str);
            return;
        }

        if(root->lchild){
            path.emplace_back(root->lchild->data);
            inner(inner, root->lchild, path);
            path.pop_back();
        }
        if(root->rchild){
            path.emplace_back(root->rchild->data);
            inner(inner, root->rchild, path);
            path.pop_back();
        }

    };
    std::vector<int> path;
    path.emplace_back(root->data);
    inner(inner, root, path);
    return all_path;
}

非递归算法，使用前序遍历的模板

std::vector<std::string> allPath(const alice::TreeNode *root){
    std::vector<std::string> all_path;
    if(root == nullptr)
        return all_path;
    std::stack<const alice::TreeNode *> stack_node;
    std::stack<std::string> stack_path;
    stack_node.push(root);
    stack_path.push(std::to_string(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();
        if(! top_node->lchild && ! top_node->rchild){
            all_path.push_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));
        }
        if(top_node->lchild){
            stack_node.push(top_node->lchild);
            stack_path.push(top_path + " -> " + std::to_string(top_node->lchild->data));
        }
    }
    return all_path;
}

1.6 左叶子之和

对于节点 A，若左孩子不为空，且左孩子的左右孩子都为空，那么节点 A 的左孩子为左叶子

判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子

递归算法，采用先序遍历

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

作业

实现左叶子之和的非递归算法