2022/04/19

Leetcode Note: Go - Symmetric Tree

Symmetric Tree - LeetCode
https://leetcode.com/problems/symmetric-tree/

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

所感

  • 再帰呼び出しが使えそうな雰囲気がある
  • しかし、シンメトリーの判定をどのように実装したら良いのだろう・・・

実装準備

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
    
}

回答

Simple recursive solution in Go - LeetCode Discuss
https://leetcode.com/problems/symmetric-tree/discuss/916411/Simple-recursive-solution-in-Go

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

func isMirror(node1 *TreeNode, node2 *TreeNode) bool {
	if node1 == nil && node2 == nil {
		return true
	}

	if node1 == nil || node2 == nil {
		return false
	}

	return node1.Val == node2.Val && isMirror(node1.Right, node2.Left) && isMirror(node1.Left, node2.Right)
}

func isSymmetric(root *TreeNode) bool {
	return isMirror(root, root)
}
  • 2つ の Node が同じか比較する isMirror 関数を実装する
    • node1 == nil and node2 == nil なら Node の内容は同じなので return true
    • node1 == nil or node2 == nil は and の次に実装しているので、実質 xor となるため Node の内容は異なると判定して return false
    • return: 以下の 3つ が全て真なら true を返す
      • node1.Val == node2.Val
        • node1 と node2 が持つ値が同じ
      • isMirror(node1.Right, node2.Left)
        • node1 の右と、 node2 の左が同じ
      • isMirror(node1.Left, node2.Right)
        • node1 の左と、 node2 の右が同じ
  • isMirror 関数に、引数で与えられる root を指定することで、最終的にシンメトリーか判定できる

熟考してれば自力でたどり着けたかも感があって悔しみがある

See Also