iOS算法题（五）如何求二叉树中的最大路径和

一 题目描述

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

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

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

示例 1:

输入: [1,2,3]

       1
      / \
     2   3

输出: 6

示例 2:

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

   -10
   / \
  9  20
    /  \
   15   7

输出: 42

二 实例讲解

作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

以下资料在群文件可自行下载！

image

三 思路

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

image

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

image

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

image

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

---

---

项目链接地址 - 05_CalculateMaxSun

作为一个开发者，有一个学习的氛围跟一个交流圈子特别重要，这是一个我的iOS交流群：413038000，不管你是大牛还是小白都欢迎入驻 ，分享BAT,阿里面试题、面试经验，讨论技术， 大家一起交流学习成长！

推荐阅读

iOS开发——最新 BAT面试题合集（持续更新中）

作者：路飞_Luck
链接：https://www.jianshu.com/p/e9c47e8530fd
来源：简书