面试热题（二叉树的最大路径）

野性酷女 2023-10-15 07:59 50阅读 0赞

> **路径** 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 **至多出现一次** 。该路径 **至少包含一个** 节点，且不一定经过根节点。
> 
> **路径和** 是路径中各节点值的总和。
> 
> 给定一个二叉树的根节点 `root` ，返回其 **最大路径和**，即所有路径上节点值之和的最大值。
> 
> ![0262b072ec15fb4a9b6730f5358c0395.jpeg][]
> 
> **输入：**root = \[1,2,3\] **输出：**6 **解释：**最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

这道题作为二叉树中的困难题，其实做起来也没有那么困难

考虑题目定义的路径的一般情形：一条路从下向上延伸，到达一个最高节点后又向下延伸，将最高点节点称为拐点，但是拐点左侧或者右侧可能没有这个节点，我们需要考虑每个节点node作为拐点，都将有一个以其拐点的最大路径之和，并由下面式子得到：

leftRree+rightTree+root.val

这里的leftTree/rightTree作为root的左右节点为该路径和带来的贡献，分别是拐点左半侧路径和拐点右半侧路径和，这道题求解过程就是考察当所有的节点作为拐点时该式的结果，最后取最大值，显然该式具有后续遍历dfs的特点（左右中），dfs()方法的参数为当前节点root,返回root作为拐点儿子的**半侧路径和**：

*  基准情形为递归到null时返回0
 *  递归得到调用dfs分别求左右儿子的leftTree和rightTree
 *  得到leftTree/rightTree后，以该式计算当前节点为拐点的最大路径max
 *  更新全局最大路径和max
 *  返回值是当前节点root作为拐点儿子的贡献值，容易有如下：

return root.val+Math.max(leftTree,rightTree);

即root将与其左右半侧路径中的较大者构成对上层拐点而言的更长的**半侧路径**

*  当dfs结束后，max中的值就是正确结果

**注意**：由于树中的节点可能都是负数，所以在取贡献的时候，如果为负数直接取0，表示该节点所在的侧路径不参与组成最大路径

源码：

//维护一个全局变量
        int max=Integer.MIN_VALUE;
        public int maxPathSum(TreeNode root) {
         //对入参进行判断
         if(root==null){
             return 0;
         }
          dfs(root);
          return max;
        }
        public int dfs(TreeNode root){
            //递归结束条件
            if(root==null){
                return 0;
            }
            int leftTree=Math.max(dfs(root.left),0);
            int rightTree=Math.max(dfs(root.right),0);
            int all=leftTree+rightTree+root.val;
            //更新最大值
            max=Math.max(max,all);
            return root.val+Math.max(leftTree,rightTree);
        }

[0262b072ec15fb4a9b6730f5358c0395.jpeg]: https://img-blog.csdnimg.cn/img_convert/0262b072ec15fb4a9b6730f5358c0395.jpeg