[Leetcode 543][Easy]-二叉树的直径-递归

目录

一、题目描述

二、整体思路

三、代码

一、题目描述

原题地址

二、整体思路

        取一个结点的最大直径就是取一个结点的左子树最大深度+右子树最大深度之和，因此可以定义一个递归函数，作用是取一个结点的最大直径。这个函数中还实现了求左子树最大深度/右子树最大深度的功能。

        容易搞不明白的是边界条件。这里我定义一个结点的左子树和右子树都为空时，该节点深度=1。

        因此，一个结点的直径=左子树根节点深度和+子树根节点深度。就不用像官方题解那样又加一又减一了。

三、代码

/**
 * 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 maxr=0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root.left==null && root.right==null){
            return 0;
        }
        go(root);
        return maxr;
    }
    public int go(TreeNode root){
        if(root==null){
            return 0;
        }
        int l=go(root.left);
        int r=go(root.right);
        maxr=Math.max(l+r,maxr);
        return Math.max(l,r)+1;
    }
}