🕌

LeetCode 872. Leaf-Similar Trees - ==演算子の配列比較

に公開
LeetCode
tech

872. Leaf-Similar Trees

https://leetcode.com/problems/leaf-similar-trees/description

Approach

再帰を使って深さ優先探索で解く。
leafノードのみを結果配列に格納し、比較する。

ruby

# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {TreeNode} root1
# @param {TreeNode} root2
# @return {Boolean}
def leaf_similar(root1, root2)
    traverse(root1) == traverse(root2)
end

def traverse(root)
  results = []
  recursion(root, results)
  results
end
def recursion(root, results)
  if !root.nil?
    recursion(root.left, results)
    results << root.val if root.left.nil? && root.right.nil?
    recursion(root.right, results)
  end
end

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def leafSimilar(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> bool:
        def traverse(root):
            results = []
            recursion(root, results)
            return results
        def recursion(root, results):
            if root is not None:
                recursion(root.left, results)
                if root.left is None and root.right is None:
                  results.append(root.val)
                recursion(root.right, results)
        
        return traverse(root1) == traverse(root2)

typescript

  • ==を使った2つの配列比較はメモリ上のアドレスを指しているかどうかで判定されるため、配列の中身は比較しない
[1,2,3] == [1,2,3]
=> false
  • 配列を文字列に変換し、判定実施する
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function leafSimilar(root1: TreeNode | null, root2: TreeNode | null): boolean {
    function traverse(root: TreeNode|null): number[]{
        let result: number[] = []

        recursion(root, result)
        return result
    }

    function recursion(root: TreeNode | null, result: number[]): void{
        if (root) {
            if(!root.left && !root.right){
                result.push(root.val)
            }
            recursion(root.left, result)
            recursion(root.right, result)
        }
    }

    return JSON.stringify(traverse(root1)) === JSON.stringify(traverse(root2));
};

golang

  • slices.Equalを使ってスライスの比較を行う
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func leafSimilar(root1 *TreeNode, root2 *TreeNode) bool {
	traverse := func(root *TreeNode) []int {
		var results []int

		var recursion func(root *TreeNode, results *[]int)
		recursion = func(root *TreeNode, results *[]int) {
			if root != nil {
				if root.Left == nil && root.Right == nil {
					*results = append(*results, root.Val)
				}
				recursion(root.Left, results)
				recursion(root.Right, results)
			}
		}

		recursion(root, &results)
		return results
	}

	return slices.Equal(traverse(root1), traverse(root2))
}

学習のポイント

  • typescriptの、==を使った2つの配列比較はメモリ上のアドレスを指しているかどうかで判定する
  • 各言語での配列比較をまとめた
言語 比較方法 備考
Ruby == 演算子
Python == 演算子
TypeScript 手動で比較関数を作成 JSON.stringifyで文字列にして一致比較を実施した
Go slices.Equal

Discussion