2022/08/01

Leetcode Note: Go - Subtree of Another Tree

Subtree of Another Tree - LeetCode
https://leetcode.com/problems/subtree-of-another-tree/

  • Go 言語で取り組んだメモ

所感

  • LinkedList root, subroot が渡されるので root に subroot が含まれているのかチェックして真なら true を return する

回答

Golang 15 lines of solution with explanations - LeetCode Discuss
https://leetcode.com/problems/subtree-of-another-tree/discuss/443079/Golang-15-lines-of-solution-with-explanations

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubtree(s *TreeNode, t *TreeNode) bool {
	if s == nil || t == nil {
		return s == t
	}

	if s.Val == t.Val && isIdentical(s, t) {
		return true
	}

	return isSubtree(s.Left, t) || isSubtree(s.Right, t)
}

func isIdentical(s, t *TreeNode) bool {
	if s == nil || t == nil {
		return s == t
	}

	return s.Val == t.Val && isIdentical(s.Left, t.Left) && isIdentical(s.Right, t.Right)
}
  • root が持つ左右のノードに対して再帰関数で判定を行う

See Also