Kotlin Leetcode - 572. Subtree of Another Tree

題目連接

class Solution {
    fun isSubtree(root: TreeNode?, subRoot: TreeNode?): Boolean {
        
    }
}

解題思路

這題可以先利用 100. Same Tree 的思路

然後遞迴判斷所有的子樹

Kotlin 參考解答

class Solution {
    fun isSubtree(root: TreeNode?, subRoot: TreeNode?): Boolean {
        return when {
            root == null && subRoot == null -> true
            root == null && subRoot != null -> false
            root != null && subRoot == null -> false
            else -> isSameTree(root, subRoot) || isSubtree(root?.left, subRoot) || isSubtree(root?.right, subRoot)
        }
    }

    private fun isSameTree(s: TreeNode?, t: TreeNode?): Boolean {
        return when {
            s == null && t == null -> true
            s == null && t != null -> false
            s != null && t == null -> false
            else -> s?.`val` == t?.`val` && isSameTree(s?.left, t?.left) && isSameTree(s?.right, t?.right)
        }
    }
}

相同的邏輯簡化後，可以改寫為

class Solution {
    fun isSubtree(root: TreeNode?, subRoot: TreeNode?): Boolean {
        return when {
            root == null -> subRoot == null
            subRoot == null -> false
            else -> isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
        }
    }

    private fun isSameTree(s: TreeNode?, t: TreeNode?): Boolean {
        return when {
            s == null -> t == null
            t == null -> false
            else -> s.`val` == t.`val` && isSameTree(s.left, t.left) && isSameTree(s.right, t.right)
        }
    }
}

---

回到 leetcode 列表