通过二叉树查找最大和路径- javascript

// 定义二叉树节点
class TreeNode {
  constructor(val, left, right) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

// 通过DFS查找最大和路径
function findMaxPathSum(root) {
  let maxSum = -Infinity;

  function dfs(node) {
    if (!node) return 0;

    // 递归计算左右子树的最大和
    const leftSum = Math.max(dfs(node.left), 0);
    const rightSum = Math.max(dfs(node.right), 0);

    // 更新最大和路径
    maxSum = Math.max(maxSum, node.val + leftSum + rightSum);

    // 返回当前节点的最大和
    return node.val + Math.max(leftSum, rightSum);
  }

  dfs(root);
  return maxSum;
}

// 创建二叉树
const 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.left = new TreeNode(6);
root.right.right = new TreeNode(7);

// 查找最大和路径
const maxPathSum = findMaxPathSum(root);
console.log("最大和路径为：" + maxPathSum);