leetcode: 100. Same Tree

문제링크

풀이1

• Recursion

class Solution {
    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
        if (p == null && q == null) return true
        if (p == null || q == null) return false
        if (p?.`val` == q?.`val`) {
            return isSameTree(p?.left, q?.left) && isSameTree(p?.right, q?.right)
        }
        return false
    }
}

풀이2

• Stack

class Solution {
    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
        val pStack = Stack<TreeNode?>()
        val qStack = Stack<TreeNode?>()
        pStack.push(p)
        qStack.push(q)
        while (pStack.isNotEmpty() && qStack.isNotEmpty()) {
            val pCurr = pStack.pop()
            val qCurr = qStack.pop()
            if (pCurr == null && qCurr == null) continue
            if (pCurr == null || qCurr == null) return false
            if (pCurr!!.`val` == qCurr!!.`val`) {
                pStack.push(pCurr!!.left)
                qStack.push(qCurr!!.left)
                pStack.push(pCurr!!.right)
                qStack.push(qCurr!!.right)
            } else return false
        }
        return true
    }
}

풀이3

• Queue

class Solution {
    fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
        val pQueue = LinkedList<TreeNode?>()
        val qQueue = LinkedList<TreeNode?>()
        pQueue.push(p)
        qQueue.push(q)
        while (pQueue.isNotEmpty() && qQueue.isNotEmpty()) {
            val pCurr = pQueue.poll()
            val qCurr = qQueue.poll()
            if (pCurr == null && qCurr == null) continue
            if (pCurr == null || qCurr == null) return false
            if (pCurr!!.`val` == qCurr!!.`val`) {
                pQueue.push(pCurr!!.left)
                qQueue.push(qCurr!!.left)
                pQueue.push(pCurr!!.right)
                qQueue.push(qCurr!!.right)
            } else return false
        }
        return true
    }
}