LeetCode 腾讯精选50题--二叉树中的最大路径和

秒速五厘米 2023-06-05 05:53 5阅读 0赞

# 二叉树中的最大路径和 #

## 题目描述 ##

给定一个非空二叉树，返回器最大路径和，路径指一条从任意节点出发，到达任意节点的序列，该路径至少包含一个节点，且不一定经过根节点

## 解题思路 ##

树这一类数据结构我还不是很熟悉，需要更进一步的学习，以下思路来自于题解：  
根据题意可知，一条最大的路径存在两种可能：

1.  存在一个节点，一条最大路径等于该节点的左右子树中路径较大的一颗子树，加上它自己后向其父节点回溯
2.  存在一个节点，一条最大路径包含其左右子树与其本身，不会再向父节点回溯

## 代码实现 ##

package algorithm.tree;
    public class MaxRoadLength {
    
        private int num = 0;
        public int maxPathSum(TreeNode root) {
    
            num = root.val;
            calculate(root);
            return num;
        }
    
        private int calculate(TreeNode root){
    
            if(root == null){
                return 0;
            }
            int leftLength = Math.max(0,calculate(root.left)); //递归获取左子树中的最大路径
            int rightLength = Math.max(0,calculate(root.right)); //递归获取右子树中的最大路径
    
            num = Math.max(num,root.val+leftLength+rightLength); //计算第二种情况下的路径长度，即左子树长度+右子树长度+节点本身的长度
            return Math.max(leftLength,rightLength)+root.val;//计算第一种情况下的路径长度，去左右子树中路径长的加上节点本身并向父节点回溯
        }
    }

转载于:https://www.cnblogs.com/Kaithy-Rookie/p/11348517.html