[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?longestpath between any two nodes in a tree. This path may or may not pass through the root. Example: 1 / 2 3 / 4 5 ? Return?3,which is the length of the path [4,2,1,3] or [5,3]. Note:?The length of path between two nodes is represented by the number of edges between them. 题意:计算一个树的最长路线,两个点之间的最长路线 这里有一点说明一下,可能过根节点,也可能不过根节点 1 / 2 3 / 4 5 ? 拿上面这个树举个例子,4213这条路线为最长路,过了根节点, 我们现在假设425是最长路线(假设不过根节点的情况),那么这个时候我们其实可以把2看做新的根节点 什么意思呢,也就是说最长路线一定是某个点的左子树高度+右子树高度,我们把每个点的这个值都算出来,找出最大的即可 class Solution { private int max = 0; private int countDiameter(TreeNode root) { if (root == null) return 0; return Math.max(countDiameter(root.right),countDiameter(root.left)) + 1; } public int diameterOfBinaryTree(TreeNode root) { if (root == null) return 0; max = Math.max(max,countDiameter(root.left) + countDiameter(root.right)); diameterOfBinaryTree(root.left); diameterOfBinaryTree(root.right); return max; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |