代码随想录第16天：513.找树左下角的值、112. 路径总和、106.从中序与后序遍历序列构造二叉树

513.找树左下角的值，层序遍历

// 找树左下角的值，用层序遍历很容易实现
#include <iostream>
#include <queue>

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

// 找到最底层最左边节点的值
int findBottomLeftValue(TreeNode *root)
{
    if (root == nullptr)
    {
        return 0; // 如果树为空，返回0（根据实际情况定义）
    }

    std::queue<TreeNode *> queue;
    queue.push(root);

    int result = 0;
    while (!queue.empty())
    {
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; ++i)
        {
            TreeNode *currentNode = queue.front();
            queue.pop();

            // 如果是当前层的第一个节点，则更新结果
            if (i == 0)
            {
                result = currentNode->val;
            }

            // 将当前节点的子节点加入队列
            if (currentNode->left != nullptr)
            {
                queue.push(currentNode->left);
            }
            if (currentNode->right != nullptr)
            {
                queue.push(currentNode->right);
            }
        }
    }

    return result;
}

int main()
{
    // 构建一个简单的二叉树作为例子
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);
    root->right->right->left = new TreeNode(7);

    // 找到最底层最左边节点的值
    std::cout << "Bottom left value: " << findBottomLeftValue(root) << std::endl;

    return 0;
}

112. 路径总和

// 路径总和
#include <iostream>

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

// 辅助函数，用于递归检查路径和
bool hasPathSum(TreeNode *node, int sum)
{
    if (node == nullptr)
    {
        return false; // 如果节点为空，直接返回 false
    }

    // 检查当前节点是否是叶子节点，并且剩余路径和是否为当前节点值
    if (node->left == nullptr && node->right == nullptr)
    {
        return sum == node->val;
    }

    // 递归检查左子树和右子树
    return hasPathSum(node->left, sum - node->val) || hasPathSum(node->right, sum - node->val);
}

// 主函数，判断树中是否存在目标路径和
bool HasPathSum(TreeNode *root, int targetSum)
{
    return hasPathSum(root, targetSum);
}

int main()
{
    // 构建一个简单的二叉树作为例子
    TreeNode *root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->left->left = new TreeNode(11);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(2);
    root->right = new TreeNode(8);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(4);
    root->right->right->right = new TreeNode(1);

    // 判断是否存在路径和为 22 的路径
    bool result = HasPathSum(root, 22);
    std::cout << "Exist path sum 22? " << (result ? "Yes" : "No") << std::endl;

    return 0;
}

106.从中序与后序遍历序列构造二叉树

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

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

TreeNode *traversal(vector<int> inorder, vector<int> posorder)
{
    if (posorder.size() == 0)
        return NULL;

    int rootValue = posorder[posorder.size() - 1];
    TreeNode *root = new TreeNode(rootValue);

    int delimiterIndex;
    for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++)
    {
        if (inorder[delimiterIndex] == rootValue)
            break;
    }

    // 切割中序数组
    vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
    vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end());

    posorder.resize(posorder.size() - 1);

    // 切割后序数组
    vector<int> leftPosorder(posorder.begin(), posorder.begin() + leftInorder.size());
    vector<int> rightPosorder(posorder.begin() + leftInorder.size(), posorder.end());

    root->left = traversal(leftInorder, leftPosorder);
    root->right = traversal(rightInorder, rightPosorder);

    return root;
}

TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
{
    if (inorder.size() == 0 || postorder.size() == 0)
        return NULL;
    return traversal(inorder, postorder);
}

void printPreorder(TreeNode *node)
{
    if (node == nullptr)
    {
        return; // 如果节点为空，则返回
    }

    std::cout << node->val << " "; // 首先打印根节点的值
    printPreorder(node->left);     // 递归打印左子树
    printPreorder(node->right);    // 递归打印右子树
}

int main()
{
    std::vector<int> inorder = {9, 3, 15, 20, 7};
    std::vector<int> postorder = {9, 15, 7, 20, 3};
    TreeNode *root = buildTree(inorder, postorder);

    printPreorder(root);
    std::cout << std::endl;
    return 0;
}