5.二叉树的直径

• 2.11
  • max 取得是 max 和 l+r（直径）进行对比更新

class Solution {
    int maxD=0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return maxD;
    }
    public int dfs(TreeNode root){
        if(root==null) return 0;
        int lD = dfs(root.left);
        int rD = dfs(root.right);
        int allD=lD+rD;
        maxD = Math.max(allD,maxD);
        return Math.max(lD,rD)+1;
    }
}

• 1.26

  • 得到左右长度，得到总长度，更新最长长度，传递给下一层长度

• 1.16

  • 道心破碎，这就是8简单题吗
  • 思路对，但细节拉完了，左长度和右长度是由 dfs 的上一层得到的（从最底层网上传递）
  • 中间记录全局直径
  • 返回值返回左右其中的最大深度+1，因为是从上一个 root 根往下传的，需要加上 root 根到目前这个节点的长度

class Solution {
    int maxDepth=0;
    public int diameterOfBinaryTree(TreeNode root) {
        getmaxDepth(root);
        return maxDepth;
    }
    public int getmaxDepth(TreeNode root){
        if(root==null) return 0;
        int leftDepth = getmaxDepth(root.left);
        int rightDepth = getmaxDepth(root.right);
        int allDepth = leftDepth+rightDepth;
        maxDepth = Math.max(maxDepth,allDepth);
        return Math.max(leftDepth,rightDepth)+1;
    }
}

• 11.11
  • 下面写的挺好,直径的本质左子树长度(max)➕右子树长度(max)
  • 在dfs的过程中记录左子树和右子树的长度,对比,返回时需要挑一个大的+1返回,因为本质还是节点的最长子树

class Solution {
    private int maxD = 0;          // 全局直径（边数）
 
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return maxD;
    }
 
    // 返回以 node 为根的子树最大深度
    private int dfs(TreeNode node) {
        if(node==null){return 0;};
        int r = dfs(node.right);
        int l = dfs(node.left);
        maxD = Math.max(maxD,r+l);
        return Math.max(r,l)+1;
 
    }
}

• 本质为左边最长的长度+右边最长的长度
• dfs返回值应该为int以返回左右各自的长度,依旧用Math.max更新最大长度,结束条件为node节点为null
• maxD为全局的长度,return的是各自左右的长度,+1代表从node节点到底的长度,而不是node节点的子树到底的长度