[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;}
}