[leetcode]543. Diameter of Binary Tree二叉树直径

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

题目

给定一棵二叉树，求任意两个节点的最长路径长度。

思路

长度的定义是边的个数，不是node的个数

跟 [leetcode]124. Binary Tree Maximum Path Sum二叉树最大路径和思路一致。

代码

 class Solution {

     public int diameterOfBinaryTree(TreeNode root) {

         /* 要么用个global variable放在class下，要么用长度为1的一维数组来存。

            这里因为求edge的数量，初始化为一维数组的default值0是可行的。

         */

         int[] diameter = new int[1];

         dfs(root, diameter);

         return diameter[0];

     }

     private int dfs(TreeNode node, int[] diameter) {

         if(node == null){return 0;}

         int lh = dfs(node.left, diameter);

         int rh = dfs(node.right, diameter);

         diameter[0] = Math.max(diameter[0], lh + rh);

         return Math.max(lh, rh) + 1;

     }

 }

巴特西

[leetcode]543. Diameter of Binary Tree二叉树直径

最新文章

热门文章