二叉树直径、最大路径和等总结

待我称王封你为后i 2023-10-04 12:03 31阅读 0赞

#### 二叉树直径、最大路径和总结 ####

*  104、二叉树的最大深度
 *  534、二叉树的直径
 *  124、二叉树中的最大路径和
 *  687、最长同值路径

今天发现这几题的解法十分类似，于是放到一起。

## 104、二叉树的最大深度 ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
     /*
    解题思路：
        很简单的递归，找到左子树和右子树的深度，取最大的，然后加上根节点的那个深度就是答案
     */
    class Solution {
        
        public int maxDepth(TreeNode root) {
        
            if(root==null){
        
                return 0;
            }
            int left=maxDepth(root.left);//左子树的深度
            int right=maxDepth(root.right);//右子树的深度
    
            return Math.max(left,right)+1;//左子树右子树那个深度大就取哪一个，再加上根节点的深度“1”.返回的就是结果
    
        }
    }

## 534、二叉树的直径 ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
     /*
    解题思路：
        这题还是在  求子树最大深度的基础上改造。求出来每个节点的左子树最大深度 和右子树最大深度后，把这两个深度加起来 就是“两个结点路径长度中的最大值”。这样再定义一个成员变量max来保存最大的那个路径长度。在每一次把每一个节点的左右子树的两个最大深度加起来后都把max和这个最大深度和进行比较，取大的值作为max。让max始终维护 节点路径长度最大，最后返回max即可
     */
    
    class Solution {
        
        int max=0;
        public int diameterOfBinaryTree(TreeNode root) {
        
            MaxDepth(root);
            return   max ;
    
        }
    
        public int MaxDepth(TreeNode root){
        
            if(root==null){
        
                return 0;
            }
    
            int left=MaxDepth(root.left);
            int right=MaxDepth(root.right);
            max=Math.max(left+right,max);//将每个节点最大直径(左子树深度+右子树深度)和当前最大值比较并取大者。也就是max始终只保留最长的路径
    
            return Math.max(left,right)+1;
        }
    }

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

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        int res=Integer.MIN_VALUE;
        public int maxPathSum(TreeNode root) {
        
            if(root==null){
        
                return 0;
            }
            dfs(root);
            return res;
        }
    
        public int dfs(TreeNode root){
        
            if(root==null){
        
                return 0;
            }
            //和0比就是说如果节点值为负数就直接不选，选了反而结果会变小
            int l_max=Math.max(0,dfs(root.left));
            int r_max=Math.max(0,dfs(root.right));
            res=Math.max(res,root.val+l_max+r_max);
    
            //返回当前节点的贡献值
            return root.val+Math.max(l_max,r_max);
    
        }
    }

## 687、最长同值路径 ##

class Solution {
        
        int res=0;
        public int longestUnivaluePath(TreeNode root) {
        
            help(root);
            return res;
        }
    
        public int help(TreeNode root){
        
            /*
            这个方法的功能就是，我传过来是左子树的时候，返回给我一个左子树的最长路径的最大值。
            用在右子树的时候同理。
            */
    
            if(root==null){
        
                return 0;
            }
            int leftCount=help(root.left);//用来保存左子树的最长路径的最大值
            int rightCount=help(root.right);//用来保存右子树的最长路径的最大值
            int left=0,right=0;//对于root来说，分别保存root左/右子树的最长路径
    
            if(root.left!=null&&root.left.val==root.val){
        //root的左子树不为空且值和root相同
                left=leftCount+1;//那么对于root来说左子树的最长路径就要+1
            }
            if(root.right!=null&&root.right.val==root.val){
        //root的右子树不为空且值和root相同
                right=rightCount+1;//那么对于root来说右子树的最长路径就要+1
            }
    
            res=Math.max(res,left+right);//注意！！更新结果在这里。对根节点来说，最长相同路径那就是左子树最长路径+右子树最长路径（假如右子树没有相同值那么right就是0，不影响最终结果）。用res来维护最大值
    
            return Math.max(left,right);//这个方法不用更改res，因为这个方法的目的是为了找出子树最长路径的最大值。 具体什么意思见CSDN
    
        }
    }