[LeetCode] Same Tree

 

🔒 Problem

 

 

🔑 BFS approach

Create two queue with bread-first search to all nodes.

To handle null case, if null, don't add left & right nodes to queue

 

BFS Code (Kotlin)

import java.util.LinkedList
import java.util.Queue

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}


class SameTree {
    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
        // 1. queue 2개 초기화 및 루트 노드 삽입
        val pQueue1 : Queue<TreeNode?> = LinkedList<TreeNode?>()
        val qQueue2 : Queue<TreeNode?> = LinkedList<TreeNode?>()

        pQueue1.add(p)
        qQueue2.add(q)
        // 2. queue 가 둘다 비어있지 않을 때 까지
        // (비어있을 수가 없는게 어차피 NULL 값 가져도 큐에는 있음)
        while (pQueue1.isNotEmpty() && qQueue2.isNotEmpty()) {
            val pNode = pQueue1.poll()
            val qNode = qQueue2.poll()

            // 3. 현재 노드 값 비교 => 다르면 return false
            // Node 가 null 인지 여부를 검사해야함
            // ? operator if null -> null return
            if (pNode?.`val` != qNode?.`val`) return false

            // 4. 현재 노드가 NULL 이 아닌 경우
            // 왼쪽 오른쪽 노드를 각각의 queue 에 push
            if (pNode != null) {
                pQueue1.add(pNode.left)
                pQueue1.add(pNode.right)
            }

            if (qNode != null) {
                qQueue2.add(qNode.left)
                qQueue2.add(qNode.right)
            }
        }

        return true
    }

}

 

 

🔑 Recursion approach

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class SameTree {
    fun isSameTreeRecursion(p: TreeNode?, q: TreeNode?): Boolean {
        // 둘다 null => leaf node 를 지나 끝자락으로 도달 => 재귀 종료 조건
        if (p == null && q == null) return true
        if (p?.`val` != q?.`val`) return false
        // preorder traversal
        return isSameTreeRecursion(p?.left, q?.left) && isSameTreeRecursion(p?.right, q?.right)
    }
}