力扣hot100刷题——41~50

41.二叉树的层序遍历

题目描述

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

思路：队列

利用队列存储每一层的节点，并不断进行更新

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
// 层序遍历
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }

    // 动态分配队列
    struct TreeNode** queue = malloc(sizeof(struct TreeNode*) * 10000);
    int front = 0, tail = 0;
    queue[front++] = root;  // 根节点入队

    // 动态分配结果数组
    int** ans = malloc(sizeof(int*) * 10000);
    *returnColumnSizes = malloc(sizeof(int) * 10000);
    *returnSize = 0;

    while (front > tail) {
        int levelSize = front - tail;  // 当前层的节点数
        ans[*returnSize] = malloc(sizeof(int) * levelSize);  // 为当前层分配空间
        (*returnColumnSizes)[*returnSize] = levelSize;  // 记录当前层的节点数

        for (int i = 0; i < levelSize; i++) {
            struct TreeNode* node = queue[tail++];  // 出队
            ans[*returnSize][i] = node->val;  // 存储节点值
            if (node->left) queue[front++] = node->left;  // 左子节点入队
            if (node->right) queue[front++] = node->right; // 右子节点入队
        }
        (*returnSize)++;  // 层数加1
    }

    free(queue);  // 释放队列
    return ans;
}

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

题目描述

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

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 按 严格递增 顺序排列

思路：递归

1. 递归终止条件：
   • 如果数组为空（numsSize == 0），返回 NULL。
2. 创建根节点：
   • 找到数组的中间元素 nums[mid]，将其作为根节点的值。
3. 递归构建左右子树：
   • 左子树由数组的左半部分（nums[0..mid-1]）构建。
   • 右子树由数组的右半部分（nums[mid+1..numsSize-1]）构建。
4. 返回根节点：
   • 返回构建好的二叉搜索树的根节点。

code

struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
    if (numsSize == 0) return NULL;  // 递归终止条件
    struct TreeNode* root = malloc(sizeof(struct TreeNode));  // 创建根节点
    int mid = numsSize / 2;  // 找到中间元素
    root->val = nums[mid];  // 中间元素作为根节点的值
    root->left = sortedArrayToBST(nums, mid);  // 递归构建左子树
    root->right = sortedArrayToBST(nums + mid + 1, numsSize - mid - 1);  // 递归构建右子树
    return root;
}

43.验证二叉搜索树

题目描述

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

• 树中节点数目范围在[1, 104] 内
• -231 <= Node.val <= 231 - 1

思路：二叉树中序遍历

BST的中序遍历序列是递增的，可以利用这个性质来判断。本题是要求严格单调递增。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool inorder(struct TreeNode* root, long long* pre) {
    if (root == NULL) return true;  // 递归终止条件
    bool res = inorder(root->left, pre);  // 递归遍历左子树
    if (root->val <= *pre) {  // 检查当前节点值是否小于等于前一个节点值
        return false;
    }
    *pre = root->val;  // 更新前一个节点值
    return inorder(root->right, pre) && res;  // 递归遍历右子树
}

bool isValidBST(struct TreeNode* root) {
    long long pre = LONG_MIN;  // 初始化前一个节点值为最小值
    return inorder(root, &pre);
}

44.二叉搜索树中的第K小的元素

题目描述

230. 二叉搜索树中第 K 小的元素

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

• 树中的节点数为 n 。
• 1 <= k <= n <= 104
• 0 <= Node.val <= 104

**进阶：**如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？

思路：中序遍历

1. 中序遍历：
   • 使用递归中序遍历二叉搜索树，将节点的值按升序存入数组 ans。
2. 返回第 k 小的元素：
   • 直接返回数组 ans 的第 k-1 个元素。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void inorder(struct TreeNode* root, int* cnt, int* ans) {
    if (root == NULL) return;  // 递归终止条件
    inorder(root->left, cnt, ans);  // 递归遍历左子树
    ans[(*cnt)++] = root->val;  // 将当前节点值存入数组
    inorder(root->right, cnt, ans);  // 递归遍历右子树
}

int kthSmallest(struct TreeNode* root, int k) {
    int* ans = malloc(sizeof(int) * 10000);  // 分配数组存储中序遍历结果
    int cnt = 0;  // 计数器
    inorder(root, &cnt, ans);  // 中序遍历
    return ans[k - 1];  // 返回第 k 小的元素
}

优化

只中序遍历前k个节点，不用将所有值都进行存储，减少空间开销。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// 中序遍历并提前终止
void inorder(struct TreeNode* root, int* cnt, int k, int* result) {
    if (root == NULL || *cnt >= k) return;  // 递归终止条件
    inorder(root->left, cnt, k, result);  // 递归遍历左子树
    (*cnt)++;  // 计数器加1
    if (*cnt == k) {  // 找到第 k 小的元素
        *result = root->val;
        return;
    }
    inorder(root->right, cnt, k, result);  // 递归遍历右子树
}

int kthSmallest(struct TreeNode* root, int k) {
    int cnt = 0;  // 计数器
    int result = 0;  // 存储结果
    inorder(root, &cnt, k, &result);  // 中序遍历
    return result;
}

45.二叉树的右视图

题目描述

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：

**输入：**root = [1,2,3,null,5,null,4]

输出：[1,3,4]

解释：

示例 2：

**输入：**root = [1,2,3,4,null,null,null,5]

输出：[1,3,4,5]

解释：

示例 3：

**输入：**root = [1,null,3]

输出：[1,3]

示例 4：

**输入：**root = []

输出：[]

提示:

• 二叉树的节点个数的范围是 [0,100]
• -100 <= Node.val <= 100

思路：层序遍历

二叉树的右视图其实就是每一层最右边的·值，通过层序遍历便可得到答案。

code

int* rightSideView(struct TreeNode* root, int* returnSize) {
    struct TreeNode* queue[100];  // 使用数组模拟队列
    int* ans = malloc(sizeof(int) * 100);  // 存储结果
    struct TreeNode* node = root;
    *returnSize = 0;  // 初始化返回数组的大小
    int front = 0;  // 队列头指针
    int tail = 0;   // 队列尾指针
    queue[front++] = node;  // 根节点入队
    if (root == NULL) return ans;  // 空树直接返回
    while (front > tail) {  // 队列不为空
        int t = front;  // 记录当前层的结束位置
        while (tail < t) {  // 遍历当前层的节点
            node = queue[tail++];  // 出队
            if (node->left) queue[front++] = node->left;  // 左子节点入队
            if (node->right) queue[front++] = node->right; // 右子节点入队
        }
        ans[(*returnSize)++] = queue[t - 1]->val;  // 当前层最右边的节点值
    }
    return ans;
}

46.二叉树展开为链表

题目描述

114. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

• 树中结点数在范围 [0, 2000] 内
• -100 <= Node.val <= 100

**进阶：**你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

思路一：利用数组

1. 先序遍历：
   • 使用递归先序遍历二叉树，将节点的值按顺序存入数组 res。
2. 构建链表：
   • 将根节点的左子树置空。
   • 从数组的第二个元素开始，依次创建新节点并连接到链表中。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void travel(struct TreeNode* root, int* res, int* cnt) {
    if (root == NULL) return;  // 递归终止条件
    res[(*cnt)++] = root->val;  // 将当前节点值存入数组
    travel(root->left, res, cnt);  // 递归遍历左子树
    travel(root->right, res, cnt);  // 递归遍历右子树
}

void flatten(struct TreeNode* root) {
    if (root == NULL) return;  // 空树直接返回
    int* res = malloc(sizeof(int) * 2000);  // 分配数组存储先序遍历结果
    int cnt = 0;  // 计数器
    travel(root, res, &cnt);  // 先序遍历
    root->left = NULL;  // 将根节点的左子树置空
    struct TreeNode* p = root;  // 当前节点指针
    for (int i = 1; i < cnt; i++) {  // 从第二个节点开始构建链表
        struct TreeNode* temp = malloc(sizeof(struct TreeNode));  // 创建新节点
        temp->val = res[i];
        temp->right = NULL;
        temp->left = NULL;
        p->right = temp;  // 将新节点连接到链表
        p = p->right;  // 移动指针
    }
}

思路二：递归

1. 递归终止条件：
   • 如果当前节点为空，直接返回。
2. 递归展开左右子树：
   • 递归调用 flatten 展开左子树和右子树。
3. 保存右子树：
   • 将当前节点的右子树保存到变量 right 中。
4. 移动左子树：
   • 将左子树移动到右子树的位置，并将左子树置空。
5. 找到右子树的末尾：
   • 使用 while 循环找到当前右子树的末尾。
6. 连接原来的右子树：
   • 将保存的右子树 right 接到当前右子树的末尾。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
void flatten(struct TreeNode* root) {
    if (root == NULL) return;  // 递归终止条件
    flatten(root->left);  // 递归展开左子树
    flatten(root->right); // 递归展开右子树
    struct TreeNode* right = root->right;  // 保存右子树
    struct TreeNode* p = root;  // 当前节点指针

    root->right = root->left;  // 将左子树移动到右子树的位置
    root->left = NULL;  // 将左子树置空
    while (p->right) {  // 找到当前右子树的末尾
        p = p->right;
    }
    p->right = right;  // 将原来的右子树接到当前右子树的末尾
}

47.从前序和中序遍历序列构造二叉树

题目描述

105. 从前序与中序遍历序列构造二叉树

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

提示:

• 1 <= preorder.length <= 3000
• inorder.length == preorder.length
• -3000 <= preorder[i], inorder[i] <= 3000
• preorder 和 inorder 均 无重复 元素
• inorder 均出现在 preorder
• preorder 保证 为二叉树的前序遍历序列
• inorder 保证 为二叉树的中序遍历序列

思路：递归

1. 创建根节点：
   • 前序遍历的第一个元素是根节点的值。
2. 在中序遍历中找到根节点的位置：
   • 遍历中序遍历数组，找到根节点的位置 index。
3. 递归构建左子树
4. 递归构建右子树
5. 返回根节点

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    if (preorderSize == 0) return NULL;  // 递归终止条件
    struct TreeNode* root = malloc(sizeof(struct TreeNode));  // 创建根节点
    root->val = preorder[0];  // 根节点的值为前序遍历的第一个元素
    int index = 0;
    for (int i = 0; i < inorderSize; i++) {  // 在中序遍历中找到根节点的位置
        if (inorder[i] == preorder[0]) {
            index = i;
            break;
        }
    }
    // 递归构建左子树
    root->left = buildTree(preorder + 1, index, inorder, index);
    // 递归构建右子树
    root->right = buildTree(preorder + 1 + index, preorderSize - index - 1, inorder + 1 + index, inorderSize - index - 1);
    return root;
}

48.路径总和Ⅲ

题目描述

437. 路径总和 III

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

提示:

• 二叉树的节点个数的范围是 [0,1000]
• -109 <= Node.val <= 109
• -1000 <= targetSum <= 1000

思路一：DFS

暴力递归：

• 对于每个节点，递归计算以该节点为起点的路径和是否等于 targetSum。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// 计算以当前节点为起点的路径和等于 targetSum 的路径数量
long long countPathsFromNode(struct TreeNode* node, long long targetSum) {
    if (node == NULL) return 0;
    long long count = 0;
    if (node->val == targetSum) count++;
    count += countPathsFromNode(node->left, targetSum - node->val);
    count += countPathsFromNode(node->right, targetSum - node->val);
    return count;
}

// 遍历每个节点，计算路径数量
long long pathSum(struct TreeNode* root, int targetSum) {
    if (root == NULL) return 0;
    return countPathsFromNode(root, targetSum) +
           pathSum(root->left, targetSum) +
           pathSum(root->right, targetSum);
}

49.二叉树的最近公共祖先

题目描述

236. 二叉树的最近公共祖先

思路：递归

1. 判断祖先关系：
   • 使用 isanc 函数判断一个节点是否是另一个节点的祖先。
   • 如果 p 是 q 的祖先，直接返回 p；如果 q 是 p 的祖先，直接返回 q。
2. 递归查找 LCA：
   • 如果 p 和 q 都在左子树中，递归到左子树查找。
   • 如果 p 和 q 都在右子树中，递归到右子树查找。
   • 如果 p 和 q 分别位于左右子树中，则当前节点就是它们的最近公共祖先。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

// 判断 node 是否是 root 的子孙节点
bool isanc(struct TreeNode* root, struct TreeNode *node) {
    if (root == NULL) return false; // 如果 root 为空，返回 false
    if (root == node) return true;  // 如果 root 就是 node，返回 true
    // 递归检查左子树和右子树
    return isanc(root->left, node) || isanc(root->right, node);
}

// 查找 p 和 q 的最近公共祖先
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL) return NULL; // 如果当前节点为空，返回 NULL

    // 如果 p 是 q 的祖先，直接返回 p
    if (isanc(p, q)) return p;
    // 如果 q 是 p 的祖先，直接返回 q
    if (isanc(q, p)) return q;

    // 如果 p 和 q 都在左子树中，递归到左子树查找
    if (isanc(root->left, p) && isanc(root->left, q)) {
        return lowestCommonAncestor(root->left, p, q);
    }
    // 如果 p 和 q 都在右子树中，递归到右子树查找
    if (isanc(root->right, p) && isanc(root->right, q)) {
        return lowestCommonAncestor(root->right, p, q);
    }

    // 如果 p 和 q 分别位于左右子树中，则当前节点就是 LCA
    return root;
}

优化

1. 递归遍历：
   • 从根节点开始递归遍历树。
   • 如果当前节点是 p 或 q，直接返回当前节点。
2. 判断左右子树：
   • 递归查找左子树和右子树。
   • 如果 p 和 q 分别在左右子树中，则当前节点就是它们的最近公共祖先。
   • 如果 p 和 q 都在左子树中，返回左子树的结果。
   • 如果 p 和 q 都在右子树中，返回右子树的结果。
3. 时间复杂度：
   • 每个节点最多被访问一次，时间复杂度为 O(n)，其中 n 是树的节点数。
4. 空间复杂度：
   • 递归栈的深度为树的高度，空间复杂度为 O(h)，其中 h 是树的高度。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL) return NULL; // 如果当前节点为空，返回 NULL

    // 如果当前节点是 p 或 q，直接返回当前节点
    if (root == p || root == q) {
        return root;
    }

    // 递归查找左子树和右子树
    struct TreeNode* left = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* right = lowestCommonAncestor(root->right, p, q);

    // 如果 p 和 q 分别在左右子树中，则当前节点是 LCA
    if (left && right) {
        return root;
    }

    // 如果 p 和 q 都在左子树中，返回左子树的结果
    if (left) {
        return left;
    }

    // 如果 p 和 q 都在右子树中，返回右子树的结果
    if (right) {
        return right;
    }

    // 如果 p 和 q 都不在当前子树中，返回 NULL
    return NULL;
}

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

提示：

• 树中节点数目在范围 [2, 105] 内。
• -109 <= Node.val <= 109
• 所有 Node.val 互不相同 。
• p != q
• p 和 q 均存在于给定的二叉树中。

50.二叉树中的最大路径和

题目描述

124. 二叉树中的最大路径和

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

提示：

• 树中节点数目范围是 [1, 3 * 104]
• -1000 <= Node.val <= 1000

思路：递归

1. 递归计算每个节点的贡献值：
   • 对于每个节点，计算其左子树和右子树的最大贡献值。
   • 节点的最大贡献值为 node->val + max(left, right)。
   • 如果子树的最大贡献值为负数，则不计入贡献值（即贡献值为 0）。
2. 计算最大路径和：
   • 对于每个节点，计算以该节点为根的最大路径和，即 node->val + left + right。
   • 更新全局最大路径和。

code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// 全局变量：存储最大路径和
int ans = INT_MIN;

// 计算当前节点的最大贡献值
int maxsum(struct TreeNode* root) {
    if (root == NULL) return 0;

    // 递归计算左右子树的最大贡献值
    int left = maxsum(root->left);
    int right = maxsum(root->right);

    // 如果子树的最大贡献值为负数，则不计入贡献值
    if (left < 0) left = 0;
    if (right < 0) right = 0;

    // 计算以当前节点为根的最大路径和
    int currentSum = root->val + left + right;

    // 更新全局最大路径和
    if (currentSum > ans) {
        ans = currentSum;
    }

    // 返回当前节点的最大贡献值
    return root->val + (left > right ? left : right);
}

int maxPathSum(struct TreeNode* root) {
    if (root == NULL) return 0;

    // 重置全局变量 ans
    ans = INT_MIN;

    // 计算最大路径和
    maxsum(root);

    return ans;
}
  - 如果子树的最大贡献值为负数，则不计入贡献值（即贡献值为 0）。
2. **计算最大路径和**：
   - 对于每个节点，计算以该节点为根的最大路径和，即 `node->val + left + right`。
   - 更新全局最大路径和。

## code

```c
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
// 全局变量：存储最大路径和
int ans = INT_MIN;

// 计算当前节点的最大贡献值
int maxsum(struct TreeNode* root) {
    if (root == NULL) return 0;

    // 递归计算左右子树的最大贡献值
    int left = maxsum(root->left);
    int right = maxsum(root->right);

    // 如果子树的最大贡献值为负数，则不计入贡献值
    if (left < 0) left = 0;
    if (right < 0) right = 0;

    // 计算以当前节点为根的最大路径和
    int currentSum = root->val + left + right;

    // 更新全局最大路径和
    if (currentSum > ans) {
        ans = currentSum;
    }

    // 返回当前节点的最大贡献值
    return root->val + (left > right ? left : right);
}

int maxPathSum(struct TreeNode* root) {
    if (root == NULL) return 0;

    // 重置全局变量 ans
    ans = INT_MIN;

    // 计算最大路径和
    maxsum(root);

    return ans;
}