《每周一道算法题》（五）二叉树中的最大路径和

一 题目描述

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

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

二 实例讲解

image.png

三 思路

1.对每一个节点都计算出：有穿过太但不穿过它父节点的最大路径和
2.整体最大路径和：1中所有计算结果的最大值

image.png

• 假设S(L)是穿过L节点但不穿过它父节点的最大路径和
• 假设V(k)是节点K能提供给父节点的最大路径值

image.png

3.1 思路1-如何求1个节点能提供给父节点的最大路径值

image.png

由此可见，求一个节点能提供给父节点的最大路径值，需要采取后序遍历左-右-root

四 代码实现

4.1 求一个节点能提供给父节点的最大路径值

/// 求一个节点能提供给父节点的最大路径值
- (int)value:(TreeNode *)node {
    if (node == nil) {
        return 0;
    }
    int leftV = MAX([self value:node.left], 0);     // 左子树节点最大路径值
    int rightV = MAX([self value:node.right], 0);   // 右子树节点最大路径值
    
    return node.value + MAX(leftV, rightV);
}

4.2 求最大路径和

static NSInteger sum = 0;

- (int)maxPathSum:(TreeNode *)root {
    [self value1:root];
    return sum;
}

/// 求最大路径和
- (int)value1:(TreeNode *)node {
    if (node == nil) {
        return 0;
    }
    int leftV = MAX([self value1:node.left], 0);     // 左子树节点最大路径值
    int rightV = MAX([self value1:node.right], 0);   // 右子树节点最大路径值
    
    // 路径累计求和
    sum = MAX(sum, node.value + leftV + rightV);
    NSLog(@"value = %d,sum = %d",node.value, sum);
    
    return node.value + MAX(leftV, rightV);
}

• 运行结果

2019-11-26 22:17:53.264435+0800 03_CheckIsValidBSTTree[9803:359884] 11
2019-11-26 22:17:53.264599+0800 03_CheckIsValidBSTTree[9803:359884] value = 1,sum = 1
2019-11-26 22:17:53.264698+0800 03_CheckIsValidBSTTree[9803:359884] value = 3,sum = 3
2019-11-26 22:17:53.264812+0800 03_CheckIsValidBSTTree[9803:359884] value = 2,sum = 6
2019-11-26 22:17:53.264918+0800 03_CheckIsValidBSTTree[9803:359884] value = 5,sum = 6
2019-11-26 22:17:53.265004+0800 03_CheckIsValidBSTTree[9803:359884] value = 4,sum = 14
2019-11-26 22:17:53.265090+0800 03_CheckIsValidBSTTree[9803:359884] value = 8,sum = 14
2019-11-26 22:17:53.265173+0800 03_CheckIsValidBSTTree[9803:359884] value = 10,sum = 14
2019-11-26 22:17:53.265264+0800 03_CheckIsValidBSTTree[9803:359884] value = 12,sum = 14
2019-11-26 22:17:53.265345+0800 03_CheckIsValidBSTTree[9803:359884] value = 11,sum = 33
2019-11-26 22:17:53.265422+0800 03_CheckIsValidBSTTree[9803:359884] value = 9,sum = 40
2019-11-26 22:17:53.265586+0800 03_CheckIsValidBSTTree[9803:359884] value = 7,sum = 48
2019-11-26 22:17:53.265773+0800 03_CheckIsValidBSTTree[9803:359884] maxSum = 48

---

本文参考MJ老师的每周一道算法题，非常感谢

---

项目链接地址 - 05_CalculateMaxSun

---

每周一道算法题 - 笔记

---