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 を指定することで、最終的にシンメトリーか判定できる

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