Leetcode题目543：二叉树的直径（简单）

题目描述：

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

示例 :
给定二叉树

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

思路分析：

对于每一个当前节点，选择左、右节点中最大的长度，然后加上1（当前路径），则是当前的最长路径深度。全局变量dis为直径，每次取左、右节点深度的和。

代码实现：

class Solution {

    //设置一个类变量，用于记录最大直径

    private int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {

        depth(root);

        return max;

    }

    private int depth(TreeNode root){

        if(root == null){

            return 0;

        }

        int leftDepth = depth(root.left);

        int rightDepth = depth(root.right);

        //max记录当前的最大直径

        max = Math.max(leftDepth + rightDepth, max);

        //由于我计算的直径是左树高度+右树高度，所以这里返回当前树的高度，以供使用

        return Math.max(leftDepth, rightDepth) + 1;

    }

}

巴特西

Leetcode题目543：二叉树的直径（简单）

最新文章

热门文章