104 二叉树的最大深度 和 543 二叉树的直径和 124 二叉树的最大路径和

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;

    }
}

543二叉树的直径和

题目

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
示例：

代码

/** * 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 = 0;
    public int diameterOfBinaryTree(TreeNode root) {
    
        dfs(root);
        return res-1;

    }
    public int dfs(TreeNode root){
    
        if(root == null)  return 0;
        int l = dfs(root.left);
        int r = dfs(root.right);
        res = Math.max(res,r+l+1);
        return Math.max(l,r)+1;
    }
}

124 二叉树的最大路径和

题目

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例：

代码

/** * 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) {
    
        getMax(root);
        return res;

    }
    public int getMax(TreeNode root){
    
        if(root == null)  return 0;
        int l = Math.max(0,getMax(root.left));
        int r = Math.max(0,getMax(root.right));
        res = Math.max(res,root.val+l+r);
        return Math.max(l,r) + root.val;

    }
}