设计一个算法判断两棵二叉树是否相似。相似只比较结构，不比较结点值。

[tag_link]

参考答案

两棵空树相似；恰有一棵为空则不相似；两棵都非空时，分别递归比较左子树和右子树的结构。结点值不参与判断。

伪代码

Similar(A, B):
    if A == null and B == null: return true
    if A == null or B == null:  return false   // 一个为空、另一个非空
    return Similar(A.left, B.left) and Similar(A.right, B.right)

复杂度

最坏时间 O(min(m,n))，其中 m、n 是两树结点数；两树规模相同且结构相似时为 O(n)。递归栈空间 O(min(h1,h2))。

边界条件

两树都空返回 true；只有一棵为空返回 false；两个单根树相似，即使保存的值不同。

易错点

相似不允许把左、右子树交叉匹配，也不是比较结点值；两个递归结果必须同时为真。

评分要点

写全两个空值出口；左右对应递归；不比较 INFO；给出复杂度。