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

原文地址：https://blog.csdn.net/2201_75413354/article/details/142380002

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！