leetcode: 100. Same Tree

kldaji·2021년 12월 14일
1

leetcode

목록 보기
7/20

문제링크

풀이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
    }
}
profile
문제해결 능력을 중요시 하는 안드로이드 개발자 입니다.

0개의 댓글