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
100. Same Tree	https://leetcode.com/problems/same-tree/	2024-01-03 16:13:00 +0800	2024-01-03 16:13:00 +0800	false	Kimi.Tsai	https://kimi0230.github.io/	0100.Same-Tree			LeetCode Go Easy Same Tree Tree	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

100. Same Tree

題目

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3] Output: true

Example 2:

Input: p = [1,2], q = [1,null,2] Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2] Output: false

Constraints:

The number of nodes in both trees is in the range [0, 100]. -104 <= Node.val <= 104

• Accepted: 1.8M
• Submissions: 3.1M
• Acceptance Rate: 60.3%

題目大意

判斷 2 顆樹是否是完全相等的

解題思路

遞歸判斷即可

Big O

時間複雜 : O(n) 空間複雜 : O(1)

來源

• https://leetcode.com/problems/same-tree/
• https://leetcode.cn/problems/same-tree/
• https://books.halfrost.com/leetcode/ChapterFour/0100~0199/0100.Same-Tree/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0100.Same-Tree/main.go

package sametree

import "LeetcodeGolang/structures"

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

type TreeNode = structures.TreeNode

// 時間複雜 O(n), 空間複雜 O(1)
func IsSameTree(p *TreeNode, q *TreeNode) bool {
	if p == nil && q == nil {
		return true
	} else if p != nil && q != nil {
		if p.Val == q.Val {
			return IsSameTree(p.Left, q.Left) && IsSameTree(p.Right, q.Right)
		}
		return false
	} else {
		return false
	}
}

Benchmark