Kotlin Leetcode - 572. Subtree of Another Tree
題目連接:https://leetcode.com/problems/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 列表