1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129  // @Title: 二叉树的直径 (Diameter of Binary Tree) // @Author: 15816537946@163.com // @Date: 2019-11-23 18:08:24 // @Runtime: 4 ms // @Memory: 4.4 MB /* * @lc app=leetcode.cn id=543 lang=golang * * [543] 二叉树的直径 * * https://leetcode-cn.com/problems/diameter-of-binary-tree/description/ * * algorithms * Easy (46.07%) * Likes: 129 * Dislikes: 0 * Total Accepted: 9.5K * Total Submissions: 20.6K * Testcase Example: '[1,2,3,4,5]' * * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 * * 示例 : * 给定二叉树 * * * ⁠ 1 * ⁠ / \ * ⁠ 2 3 * ⁠ / \ * ⁠ 4 5 * * * 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 * * 注意：两结点之间的路径长度是以它们之间边的数目表示。 * */ /** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ /* func diameterOfBinaryTree(root *TreeNode) int { _, res := helper(root) return res } func helper(node *TreeNode) (length, diameter int) { if node == nil { return } leftLen, leftDia := helper(node.Left) rightLen, rightDia := helper(node.Right) length = max(leftLen, rightLen) + 1 diameter = max(leftLen+rightLen, max(leftDia, rightDia)) return } func max(a, b int) int { if a > b { return a } return b } */ /* func diameterOfBinaryTree(root *TreeNode) int { _, res := helper(root) return res } func helper(node *TreeNode) (length, diameter int) { if node == nil { return } leftLen, leftDia := helper(node.Left) rightLen, rightDia := helper(node.Right) length = max(leftLen, rightLen) + 1 diameter = max(leftLen+rightLen, max(leftDia, rightDia)) return } func max(a, b int) int { if a > b { return a } return b } */ func diameterOfBinaryTree(root *TreeNode) int { _, res := helper(root) return res } func helper(root *TreeNode) (length, diameter int) { if root == nil { return } leftLen, leftDia := helper(root.Left) rightLen, rightDia := helper(root.Right) length = max(leftLen, rightLen)+1 diameter = max(leftLen+rightLen, max(leftDia,rightDia)) return } func max(a,b int) int { if a > b { return a } return b }