Same Tree
环境：python 3.6，scala 2.11.8
题意
判断两颗二叉树是否相同（结构相同 + 各节点值相同）。
分析
首先，题意非常明确：当两颗树结构相同、各节点值相同时，则称这两棵树相同。因此，用集合装载节点值、判断集合中元素值是否相同无法通过，它无法判断结构是否相同。
-
选定上述一种遍历方式后，可在遍历过程中判断：
两颗树只有其中一颗树有子节点，则说明两树不同；
-
两个树都有子节点：
节点值不同，则说明两树不同；
节点值相同，继续遍历；
代码
python
def isSameTree(p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
def dfs(node1, node2):
if not node1 and not node2: return True
if not node1 or not node2: return False
return node1.val == node2.val and dfs(node1.left, node2.left) and dfs(node1.right, node2.right)
return dfs(p, q)
def isSameTreeV2(p, q):
if not p and not q: return True
if not p or not q: return False
return p.val == q.val and isSameTreeV2(p.left, q.left) and isSameTreeV2(p.right, q.right)
def isSameTreeV3(p, q):
if not p and not q: return True
if not p or not q: return False
s1, s2 = [p], [q]
while s1 and s2:
node1, node2 = s1.pop(), s2.pop()
if node1 and node2:
if node1.val != node2.val:
return False
s1.append(node1.right)
s1.append(node1.left)
s2.append(node2.right)
s2.append(node2.left)
elif node1 or node2:
return False
return True
scala
import scala.collection.mutable.Stack
object LC100 {
def isSameTree(p: TreeNode, q: TreeNode): Boolean =
(p, q) match {
case (null , null) => true
case (_, null) | (null, _) => false
case _ => p.value == q.value & isSameTree(p.left, q.left) & isSameTree(p.right, q.right)
}
def isSameTreeV2(p: TreeNode, q: TreeNode): Boolean = {
if (p == null & q == null) return true
if (p == null | q == null) return false
val (s1, s2) = (Stack(p), Stack(q))
while (s1.nonEmpty & s2.nonEmpty) {
val (node1, node2) = (s1.pop(), s2.pop())
if (node1 != null & node2 != null) {
if (node1.value != node2.value) return false
s1.push(node1.right)
s1.push(node1.left)
s2.push(node2.right)
s2.push(node2.left)
} else if (node1 != null | node2 != null )
return false
}
true
}
}
最后
欢迎交流和补充
