README.md

title	subtitle	date	lastmod	draft	author	authorLink	description	license	images	tags	categories	featuredImage	featuredImagePreview	hiddenFromHomePage	hiddenFromSearch	twemoji	lightgallery	ruby	fraction	fontawesome	linkToMarkdown	rssFullText	toc	code	math	mapbox	share	comment	library	seo
0543. Diameter of Binary Tree	https://leetcode.com/problems/diameter-of-binary-tree/	2023-01-22 21:20:00 +0800	2023-01-22 21:20:00 +0800	false	Kimi.Tsai	https://kimi0230.github.io/	0543.Diameter-of-Binary-Tree			LeetCode Go Easy Diameter of Binary Tree DFS	LeetCode			false	false	false	true	true	true	true	false	false	enable auto true true	copy maxShownLines true 200	enable		enable true	enable true	css js	images

543. Diameter of Binary Tree

題目

Given the root of a binary tree, return 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.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3]. Example 2:

Input: root = [1,2] Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 104]. -100 <= Node.val <= 100

題目大意

解題思路

左邊的最高高度與右邊的最高高度相加

Big O

時間複雜 O(n), 空間複雜: 最壞 O(n), 平衡樹 O(log(n))

來源

• https://leetcode.com/problems/diameter-of-binary-tree/
• https://leetcode.cn/problems/diameter-of-binary-tree/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0543.Diameter-of-Binary-Tree/main.go

package diameterofbinarytree

import "LeetcodeGolang/structures"

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type TreeNode = structures.TreeNode

var maxDiameter int

// 時間複雜 O(n), 空間複雜: 最壞 O(n), 平衡樹 O(log(n))
func DiameterOfBinaryTree(root *TreeNode) int {
	if root == nil {
		return 0
	}
	maxDiameter = 0
	maxDepth(root)
	return maxDiameter
}

func maxDepth(node *TreeNode) int {
	if node == nil {
		return 0
	}
	left := maxDepth(node.Left)
	right := maxDepth(node.Right)

	maxDiameter = max(maxDiameter, left+right)
	return max(left, right) + 1
}

func max(a, b int) int {
	if a >= b {
		return a
	} else {
		return b
	}
}

Benchmark