sakura 技术分享 2022-06-16

javaScript 二叉树若干算法题分析（下）

上文讲到二叉树的一些遍历和高度，今天讲讲二叉树的路径与价值问题。

1、二叉树中和为某一值的路径

给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

例如：

{5,4,8,1,11,#,9,#,#,2,7},22
// true

思路：必须从根节点到每个叶节点，和值进行比较，如果存在某个分支和值相等，保存true到最终结果。

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
 }

function recursion(s, node, sum, bool) {
    s += node.val
    if (!node.left && !node.right) {  // 叶节点
        return s === sum
    }
    // 使用 || 来获取任何一个true，否则false
    if (node.left) {
        bool = bool || recursion(s, node.left, sum)
    }
    if (node.right) {
        bool = bool || recursion(s, node.right, sum)
    }
    return bool
}
/**
  * @param root TreeNode类 
  * @param sum int整型 
  * @return bool布尔型
  */
function hasPathSum( root ,  sum ) {
    // write code here
    if (!root) return false
    return recursion(0, root, sum, false)
}

// 测试
let root = new TreeNode(5)
root.left = new TreeNode(4)
root.left.left =  new TreeNode(1)
root.left.right = new TreeNode(11)
root.left.right.left = new TreeNode(2)
root.left.right.right = new TreeNode(7)
root.right = new TreeNode(8) 
root.right.right = new TreeNode(9)

console.log('arr-',hasPathSum(root, 22)) 

module.exports = {
    hasPathSum : hasPathSum
};

2、（较难）二叉树中最大路径和

二叉树里面的路径被定义为:从该树的任意节点出发，经过父=>子或者子=>父的连接，达到任意节点的序列。

注意:

1.同一个节点在一条二叉树路径里中最多出现一次

2.一条路径至少包含一个节点，且不一定经过根节点

给定一个二叉树的根节点root，请你计算它的最大路径和

数据范围：节点数满足 0≤n≤105 ，节点上的值满足 |val| ≤1000

要求：空间复杂度 O(1)，时间复杂度 O(n)

例如

// 输入 {-20,8,20,#,#,15,6}
// 输出 41   
//其中一条最大路径为:15=>20=>6，路径和为15+20+6=41

思路要想整体获得最大和，每个节点都应该计算当前节点作为根节点的最大和。递归无疑了。

叶节点的最大和就是节点值本身，（如果值是负值，则在父节点里就不应该包含此点值，否则收益就要减少），非叶节点最大和则为自己加上左右节点的最大和。

递归如何传递参数，返回值应该为什么？

1、首先，父节点需要子节点什么数据？子节点的最大和吗？应该是“最大贡献”。这里的贡献指的是，子节点将和父节点一起合并成一个更大的路径，以便于确定父节点最大和。形成路径的条件只能是每个节点选择左边或者选择右边。最大贡献是在子节点选择左边和选择右边中选择更大的一个和值。比如 {1, 3, 4} ,最大贡献是Math.max(1+3, 1+4) 即选择右边。所以递归应该返回的是每个节点最大贡献。

2、我们还需要将每个节点最大和进行比较，选择更大那个。直到递归完所有节点，就应该得到最大的那个最大和。这个变量可以使用全局变量存储，每经过一个点，就和这个点的最大和比较，选择更大的值作为这个变量的值。

3、这么看来，已经可以确定下来，递归的方式，参数应该只需要每个节点本身了。

function TreeNode(x) {
   this.val = x;
   this.left = null;
   this.right = null;
}
// 定义一个全局变量，作为最大和
// 考虑到节点值可能为负值，所以最大和可能为负数，要获取更大的负数，只能和-Infinity比较了
let maxSum = -Infinity
// 递归
function solution(node) {
    if(!node) return 0   // base case 叶节点贡献为0
    
    // 获取子节点的最大贡献，负数则取0，表示：不连接此路径，负贡献不计算在最大和之内
    let leftgain = Math.max( solution(node.left), 0 )
    let rightgain = Math.max( solution(node.right), 0 )
    
       // 比较全局最大和 和 当前节点最大和 ，选择更大那个作为全局最大和
    let thisMax = node.val + leftgain + rightgain
    maxSum = Math.max(maxSum, thisMax)
    
    // 返回当前节点的最大贡献，有可能是负数
    return node.val + Math.max(leftgain, rightgain)
    
}
/**
  * 
  * @param root TreeNode类 
  * @return int整型
  */
function maxPathSum( root ) {
    // write code here
    solution(root)
    return maxSum
}

let node = new TreeNode(-20)
node.left = new TreeNode(8)
node.right = new TreeNode(-20)
node.right.left = new TreeNode(15)
node.right.right = new TreeNode(50)
node.right.left.left = new TreeNode(10)
node.right.left.right = new TreeNode(17)

maxPathSum(node)
console.log('maxSum--',maxSum)  // 62
module.exports = {
    maxPathSum : maxPathSum
};