🏷️ 知识点：Ds.05.03.01

关于二叉树遍历的说法（引用：将求中序第一个结点函数中的ltag/lchild替换为rtag/rchild并向右下查找可求中序最后结点；将求中序后继函数中的rtag/rchild替换为ltag/lchild并调用左子树中序最后结点可求前驱），正确的是（ ）。

A. 中序最后结点一定是先序最后结点 B. 中序最后结点一定是根 C. 中序最后结点为叶时先序最后结点与其相同 D. 先序最后结点一定在中序最后结点右侧

[tag_link]

correct answer: C

结论

中序末结点沿右链；若为叶则先序也最后访问它。

推导

沿左右子树定义判断。

易错点

混淆先序/中序末结点。

二叉树根a的左孩子为b、右孩子为c，三种遍历中结点b和c的访问关系是（ ）。

A. b一定在a前 B. a一定在c前 C. b一定在c前 D. a一定在b前

[tag_link]

correct answer: C

结论

b必早于c。

推导

三种DFS均先完整左子树再右子树。

易错点

误把根访问时机影响左右顺序。

若结点n在结点m之前被中序遍历访问，则两结点位置关系是（ ）。

A. n在m右方 B. n为m祖先 C. n在m左方 D. n为m子孙

[tag_link]

correct answer: C

结论

n在m左方。

推导

中序是左、根、右。

易错点

误判为祖先。

设n、m为二叉树结点，后序遍历时n在m前的充分条件是（ ）。（A、B在ZIP与DOCX权威源均缺失，保留待补占位，不据此猜测。）

A. 权威源缺失待补 B. 权威源缺失待补 C. n在m左方 D. n是m的子孙

[tag_link]

correct answer: D

结论

D，A/B待权威补齐。

推导

后序LRN中子孙先于祖先。

易错点

猜测缺失选项。

已知一棵二叉树按顺序存储的一维稀疏数组表示：

其后序遍历序列为（ ）。

A. ghbefhca B. gbdehcfa C. gdbhefca D. bgdehcfa

[tag_link]

correct answer: C

结论

C，后序为gdbhefca。

推导

索引0:a、1:b、2:c、4:d、5:e、6:f、9:g、12:h；左子树后序g,d,b，右子树后序h,e,f,c，最后根a，合并为gdbhefca。

易错点

把空槽当作结点。

三种遍历中叶结点的相对访问顺序（ ）。

A. 都不相同 B. 完全相同 C. 先序中序相同而与后序不同 D. 中序后序相同而与先序不同

[tag_link]

correct answer: B

结论

B，叶序完全相同。

推导

叶结点均从左到右访问。

易错点

误以为叶序改变。

按编号要求父结点编号大于孩子且左孩子编号小于右孩子，应采用（ ）。

A. 先序 B. 中序 C. 后序 D. 层序

[tag_link]

correct answer: C

结论

C，后序。

推导

孩子先父后且左先右。

易错点

误选层序。

按题给编号公式v=左子树最小−1、右子树最小=左子树最大+1，应采用先序遍历（ ）。

A. 中序 B. 先序 C. 后序 D. 层序

[tag_link]

correct answer: B

结论

B，先序。

推导

公式体现NLR连续编号。

易错点

写成中序。

先序序列ABC、后序序列CBA的二叉树共有（ ）棵。

A. 1 B. 2 C. 3 D. 4

[tag_link]

correct answer: D

结论

D，4棵。

推导

单支链两条边各有左右选择，2²=4。

易错点

漏计左右组合。

完全二叉树后序序列为CDBFGEA，其先序序列是（ ）。

A. CBDAFEG B. ABECDFG C. ABCDEFG D. 无法确定

[tag_link]

correct answer: C

结论

C，ABCDEFG。

推导

完全7结点形态固定后切分。

易错点

直接倒置后序。

若先序中X在Y之前且后序中X在Y之后，则X与Y关系为（ ）。

A. 左兄弟 B. 右兄弟 C. 祖先 D. 后裔

[tag_link]

correct answer: C

结论

C，X是Y祖先。

推导

先序X前且后序X后包围Y。

易错点

颠倒祖先方向。

若先序中出现a…b而中序中出现b…a，则（ ）。

A. a、b分处某结点左右子树 B. b在a右子树 C. b在a左子树 D. a、b分处某结点两棵非空子树

[tag_link]

correct answer: C

结论

C，b在a左子树。

推导

先序a前、中序b前定位左子树。

易错点

混用遍历方向。

一棵二叉树的先序遍历序列为1234567，它的中序遍历序列可能是（　　）。

A. 3124567 B. 1234567 C. 4135627 D. 1463572

[tag_link]

正确答案：B

结论

根为1；中序1234567对应全右斜树，合法。

推导

根为1；中序1234567对应全右斜树，合法。

易错点

把任意中序序列误当作可由该先序构造

下列序列中，不能唯一地确定一棵二叉树的是（　　）。

A. 层次序列和中序序列 B. 先序序列和中序序列 C. 后序序列和中序序列 D. 先序序列和后序序列

[tag_link]

正确答案：D

结论

先序/中序或后序/中序可递归唯一构造，先序+后序不能唯一划分左右子树。

推导

先序/中序或后序/中序可递归唯一构造，先序+后序不能唯一划分左右子树。

易错点

忽略单子树时左右方向不确定

若一棵二叉树的中序序列和后序序列相同，则（　　）。

A. 二叉树为空树或任一结点没有左子树 B. 二叉树为空树或任一结点没有右子树 C. 二叉树为空树或每个结点的度为1 D. 二叉树为空树或为满二叉树

[tag_link]

正确答案：B

结论

中序=后序当且仅当每个结点无右子树。

推导

中序=后序当且仅当每个结点无右子树。

易错点

把中序与后序相同误判为无左子树

已知一棵二叉树的后序序列为DABEC，中序序列为DEBAC，则先序序列为（　　）。

A. ACBED B. DECAB C. DEABC D. CEDBA

[tag_link]

正确答案：D

结论

后序根C，左根E，E左D右B且B右A，先序CEDBA。

推导

后序根C，左根E，E左D右B且B右A，先序CEDBA。

易错点

只按序列首元素确定后序根

已知一棵二叉树的先序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（　　）。

A. CBEFDA B. FEDCBA C. CBEDFA D. 不确定

[tag_link]

正确答案：A

结论

根A；左B-C，右D-E/F，后序CBEFDA。

推导

根A；左B-C，右D-E/F，后序CBEFDA。

易错点

混淆先序和后序的根位置

已知一棵二叉树的层次序列为ABCDEF，中序序列为BADCFE，则先序序列为（　　）。

A. ACBEDF B. ABCDEF C. BDFECA D. FCEDBA

[tag_link]

正确答案：B

结论

层序根A、左B，右子树根C，先序ABCDEF。

推导

层序根A、左B，右子树根C，先序ABCDEF。

易错点

只按层序顺序直接当先序

某二叉树中结点x在先序、中序、后序遍历序列中的编号分别为pre(x)、in(x)、post(x)（均从1开始）。a是b的祖先，则不可能出现的是（　　）。

A. pre(a)<pre(b) B. post(a)<post(b) C. in(a)<in(b) D. in(a)>in(b)

[tag_link]

正确答案：B

结论

祖先必pre(a)<pre(b)、post(a)>post(b)，故B不可能。

推导

祖先必pre(a)<pre(b)、post(a)>post(b)，故B不可能。

易错点

把后序访问方向记反

某二叉树采用二叉链表存储结构，若要删除并释放所有结点，采用（　　）遍历最合适。

A. 中序 B. 层次 C. 后序 D. 先序

[tag_link]

正确答案：C

结论

后序先处理左右子树再处理根，释放安全。

推导

后序先处理左右子树再处理根，释放安全。

易错点

先释放根再访问子树

某二叉树T的中序遍历为升序，操作后得到T’，要求T’的中序为降序，正确的是（　　）。

A. 采用中序遍历最合适 B. 采用后序遍历最合适 C. T’根一定不是原T根 D. T’叶结点不一定是原T叶结点

[tag_link]

正确答案：B

结论

交换左右子树反转中序，应自底向上后序处理。

推导

交换左右子树反转中序，应自底向上后序处理。

易错点

T’符号混乱或误以为根/叶必改变

某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）。

A. 空或只有一个结点 B. 高度等于其结点数 C. 任意一个结点无左孩子 D. 任意一个结点无右孩子

[tag_link]

correct answer: B

结论

NLR与LRN互反要求每个结点至多一个孩子，形成单支树，高度等于结点数。

推导

若某结点同时有左右子树，先序在根后先进入左子树，而反转后的后序在根后先对应右子树，二者不可能逐项相同。因此每个结点至多有一个孩子，整棵树是单支链，高度等于结点数。

易错点

单支方向可混合，非必然全左或全右。

某非空二叉树的先序序列和中序序列正好相反，则正确的是（ ）。

A. 一定只有一个结点 B. 只有一个叶结点的二叉树一定满足 C. 任意一个结点无左孩子的二叉树一定满足 D. 任意一个结点无右孩子的二叉树一定满足

[tag_link]

correct answer: D

结论

NLR与LNR相反时每个非叶无右孩子，故D。

推导

先序为“根、左、右”，中序为“左、根、右”。要让两序列互为逆序，每个非叶结点都只能把后续结点放在左侧；若存在右孩子，右子树在两序列中的相对位置无法满足反序。因此所有非叶结点均无右孩子。

易错点

只有一个叶结点不能保证方向。

【2017统考真题】要使非空二叉树的先序序列与中序序列相同，其所有非叶结点须满足（ ）。

A. 只有左子树 B. 只有右子树 C. 结点的度均为1 D. 结点的度均为2

[tag_link]

correct answer: B

结论

先序根左右与中序左根右相同要求左子树为空，即只有右子树。

推导

先序在访问子树时先访问根，中序会先访问左子树。两序列要从每一层起都相同，当前结点的左子树必须为空；递归到各层后，所有非叶结点都只能有右子树。

易错点

度为1不区分左右方向。

若某非空二叉树的先序序列和后序序列正好相反，则该二叉树的形态是什么？

[tag_link]

参考答案

该树必为单支链：每个结点至多有一个孩子，孩子可以在左侧或右侧；若有 n 个结点，则 height = n。

伪代码

ShapeFromOrders(pre, post):
    n = length(pre)
    if n == 0 or length(post) != n: return INVALID
    if pre != reverse(post): return NOT_THIS_CASE
    return SINGLE_CHAIN, height = n

复杂度

比较序列需 O(n) 时间；若题设已保证两序列互逆，只判断形态可视为 O(1)。双指针比较的额外空间为 O(1)。

边界条件

题设为非空树；n=1 时单个根结点也是单支链。默认结点值可区分，否则仅凭值序列无法逐项识别结点。

易错点

不能进一步断言是全左斜树或全右斜树，单支链的方向可以逐层改变。

评分要点

指出每个结点至多一个孩子；说明左右子树同时存在会破坏逆序关系；给出高度为 n。

若某非空二叉树的先序序列和后序序列正好相同，则该二叉树的形态是什么？

[tag_link]

参考答案

在结点值互异且二叉树非空的前提下，该树仅有一个根结点。只要存在第二个结点，先序首项是根而后序首项必不是根，两序列就不可能相同。

伪代码

ShapeWhenEqual(pre, post):
    if length(pre) != length(post) or pre != post: return NOT_THIS_CASE
    if size(T) == 1: return ONLY_ROOT
    return IMPOSSIBLE

复杂度

逐项比较需 O(n) 时间，额外空间 O(1)。

边界条件

空树也会得到两个空序列，但题目明确非空；n=1 时成立。结点值应能唯一标识结点。

易错点

不要把“先序与后序不能唯一确定一般二叉树”误用到本题；这里要求两个完整序列逐项相同。

评分要点

利用根在先序首位、后序末位；排除 n>1；得出仅有一个根结点。

假设二叉树采用二叉链表存储结构，设计一个非递归算法求二叉树的高度。

[tag_link]

参考答案

使用队列层序遍历。last 指向当前层最后一个结点，nextLast 记录下一层最后入队的结点；弹出 last 时层数 level 加 1。

伪代码

Height(T):
    if T == null: return 0
    Q.enqueue(T); level = 0; last = T; nextLast = null
    while not Q.empty():
        p = Q.dequeue()
        if p.left  != null: Q.enqueue(p.left);  nextLast = p.left
        if p.right != null: Q.enqueue(p.right); nextLast = p.right
        if p == last:
            level = level + 1
            last = nextLast
    return level

复杂度

每个结点入队、出队一次，时间 O(n)；队列最多保存一层结点，空间 O(w)，w 为最大宽度。

边界条件

空树高度返回 0；单结点树返回 1。nextLast 只在孩子入队时更新，最后一层没有孩子也不影响循环结束。

易错点

不能用队列长度的瞬时值直接当高度；更新 last 必须发生在当前层最后结点处理完之后。

评分要点

给出队列；正确维护 level、last、nextLast；处理空树；写出 O(n) 与 O(w)。

二叉树按二叉链表形式存储，试编写一个判别给定二叉树是否为完全二叉树的算法。

[tag_link]

参考答案

层序扫描时把左右空指针也入队。一旦遇到第一个空位置，后续队列中若再出现非空结点，就说明层序编号出现空洞，该树不是完全二叉树。

伪代码

IsComplete(T):
    if T == null: return true
    Q.enqueue(T); seenNull = false
    while not Q.empty():
        p = Q.dequeue()
        if p == null:
            seenNull = true
        else:
            if seenNull: return false
            Q.enqueue(p.left)      // 空指针也入队
            Q.enqueue(p.right)
    return true

复杂度

每个真实结点及其边界空指针至多处理一次，时间 O(n)，队列空间 O(n)，通常记为 O(w)。

边界条件

空树通常视为完全二叉树；单结点树成立；只有左孩子成立，只有右孩子不成立。

易错点

只把非空孩子入队会丢失空位信息，从而把“右边仍有结点”的非法结构误判为完全。

评分要点

采用层序；空指针入队；首空后拒绝非空；覆盖空树和单侧孩子。

假设二叉树采用二叉链表存储结构，设计一个算法计算给定二叉树中双分支结点（度为 2 的结点）的数量。

[tag_link]

参考答案

递归统计左右子树，再在当前结点左右孩子都非空时加 1。

伪代码

CountDegree2(T):
    if T == null: return 0
    self = 1 if T.left != null and T.right != null else 0
    return self + CountDegree2(T.left) + CountDegree2(T.right)

复杂度

每个结点访问一次，时间 O(n)；递归栈空间 O(h)，最坏 O(n)。

边界条件

空树返回 0；叶结点和只有一个孩子的结点都不计数。

易错点

“双分支结点”要求两个孩子均存在，不能把度为 1 的结点算入，也不能使用逻辑或。

评分要点

空树递归出口；左右孩子同时非空才加 1；合并两棵子树计数；复杂度正确。

设 B 是一棵采用链式结构存储的二叉树，编写一个交换 B 中所有结点左、右子树的函数。

[tag_link]

参考答案

采用后序思想，先递归处理左右子树，再交换当前结点的两个孩子指针，可原地得到镜像树。

伪代码

SwapChildren(T):
    if T == null: return
    SwapChildren(T.left)          // 先递归处理左右子树
    SwapChildren(T.right)
    temp = T.left
    T.left = T.right
    T.right = temp

复杂度

时间 O(n)，递归栈空间 O(h)。

边界条件

空树无需操作；单结点树不变；对结果再执行一次该算法会恢复原树。

易错点

若先交换当前结点再仍按旧指针含义递归，容易重复处理一侧或漏掉另一侧；后序写法最稳妥。

评分要点

遍历全部结点；每个结点只交换一次；递归出口正确；说明原地修改与复杂度。

假设二叉树采用二叉链表存储结构，设计一个算法，求先序遍历序列中第 k 个结点的值。

[tag_link]

参考答案

按根、左、右的顺序递归访问，用 counter 记录已访问结点数；counter 首次等于 k 时返回当前结点并立即停止后续搜索。

伪代码

KthPreorder(T, k):
    if k < 1: return null
    counter = 0
    return Visit(T)

Visit(T):
    if T == null: return null
    counter = counter + 1
    if counter == k: return T
    found = Visit(T.left)
    if found != null: return found
    return Visit(T.right)

复杂度

找到前访问 k 个结点，时间 O(k)；最坏或 k 超出时为 O(n)。递归栈空间 O(h)。

边界条件

k<1 或 k 超出结点总数都返回 null；空树返回 null；k=1 返回根。

易错点

counter 必须按一次完整查询初始化，且找到后要短路返回，不能继续遍历并覆盖结果。

评分要点

体现先序次序；正确更新 counter；找到即返回；处理 k 非法或 k 超出；复杂度正确。

已知二叉树以二叉链表存储。编写算法：删除树中每个元素值为 x 的结点所对应的整棵子树，并释放相应空间。

[tag_link]

参考答案

主过程按引用接收子树根指针。遇到值为 x 的结点时，后序释放其整棵子树并把该父链接改为空；随后不再进入已释放区域。

伪代码

Destroy(ref T):
    if T == null: return
    Destroy(ref T.left)
    Destroy(ref T.right)
    free(T)
    T = null

RemoveX(ref T, x):
    if T == null: return
    if T.data == x:
        Destroy(ref T)
        return
    RemoveX(ref T.left, x)
    RemoveX(ref T.right, x)

复杂度

每个仍可达结点最多访问或释放一次，时间 O(n)；递归栈空间 O(h)。

边界条件

根值为 x 时整棵树被删除；空树直接返回；若祖先已匹配 x，无需再分别寻找其后代中的 x。

易错点

必须先释放孩子再释放根，并通过引用把父结点的对应孩子指针置空，否则会产生悬空指针或释放后访问。

评分要点

后序 Destroy；命中 x 后删除整棵子树；断开父链接；避免二次访问；说明复杂度。

在二叉树中查找值为 x 的结点，编写非递归后序遍历算法打印该结点的所有祖先。假设值为 x 的结点至多一个。

[tag_link]

参考答案

用单栈和 lastVisited 模拟后序遍历。当目标结点准备出栈时，它的全部祖先仍按“根到双亲”的顺序保留在栈中，直接打印即可。

伪代码

PrintAncestors(root, x):
    stack = empty; p = root; lastVisited = null
    while p != null or not stack.empty():
        while p != null:
            stack.push(p)
            p = p.left
        top = stack.peek()
        if top.right != null and lastVisited != top.right:
            p = top.right
        else:
            stack.pop()
            if top.data == x:
                print stack from bottom to top      // 栈中从底到顶
                return true
            lastVisited = top
    return false

复杂度

最坏访问全部结点，时间 O(n)；栈空间 O(h)。打印本身另需 O(h) 时间。

边界条件

根就是 x 时打印空序列并返回 true；空树或 x 不存在返回 false；题设保证至多一个 x。

易错点

目标出栈后再打印会丢失祖先；应利用尚未弹出的栈内容，并且不要把目标自身打印为祖先。

评分要点

正确模拟非递归后序；识别右子树是否已访问；利用栈输出祖先；处理根和不存在。

二叉树结点含 LLINK、INFO、RLINK 三个域，ROOT、p、q 分别指向根和任意两个目标结点。编写 ANCESTOR(ROOT, p, q, r)，求 p 与 q 的最近公共祖先 r。

[tag_link]

参考答案

分别用 DFS 求根到 p、q 的路径；只有两条路径都存在时，扫描最后一个相同结点，它就是最近公共祖先。

伪代码

FindPath(T, target, path):
    if T == null: return false
    path.push(T)
    if T == target: return true
    if FindPath(T.left, target, path) or FindPath(T.right, target, path): return true
    path.pop()
    return false

Ancestor(root, p, q):
    pathP = []; pathQ = []
    foundP = FindPath(root, p, pathP)
    foundQ = FindPath(root, q, pathQ)
    if not foundP or not foundQ: return null
    r = null
    for i = 0 while i < min(length(pathP), length(pathQ)) and pathP[i] == pathQ[i]:
        r = pathP[i]
    return r

复杂度

两次 DFS 的时间 O(n)，两条路径和递归栈空间 O(h)。

边界条件

p 或 q 不在树中时返回 null；p=q 时返回该结点；其中一个目标是根时最近公共祖先为根；空树返回 null。

易错点

只根据值比较可能混淆重复值结点，本题参数是结点指针，应比较结点身份；还必须确认两个目标都存在。

评分要点

两次路径搜索；回溯时弹栈；校验 foundP/foundQ；取最长公共前缀末结点；覆盖根和缺失目标。

假设二叉树采用二叉链表存储结构，设计一个算法求非空二叉树 b 的宽度（结点数最多的一层的结点数）。

[tag_link]

参考答案

逐层 BFS。每轮先记录当前队列长度 levelSize，它就是本层宽度，再处理恰好 levelSize 个结点并将下一层孩子入队。

伪代码

Width(T):
    if T == null: return 0
    Q.enqueue(T); maxWidth = 0
    while not Q.empty():
        levelSize = Q.size()
        maxWidth = max(maxWidth, levelSize)
        repeat levelSize times:
            p = Q.dequeue()
            if p.left  != null: Q.enqueue(p.left)
            if p.right != null: Q.enqueue(p.right)
    return maxWidth

复杂度

时间 O(n)；队列最多容纳一层及相邻层的部分结点，空间 O(w)，w 为最大宽度。

边界条件

空树返回 0；题设非空时结果至少为 1；不能把空指针计入层宽。

易错点

必须在本层出队前固定 levelSize；若边入队边读取变化后的队长，会把下一层结点混入本层。

评分要点

层序遍历；固定每层结点数；维护 maxWidth；处理空树；复杂度正确。

设有一棵满二叉树（所有结点值均不同），已知其先序序列 pre，设计一个算法求后序序列 post。

[tag_link]

参考答案

满二叉树的左右子树结点数相等。长度为 n 的当前先序片段以根开头，其后各有 m=(n-1)/2 个结点属于左右子树；递归转换后把根写到后序片段末尾。

伪代码

PreToPost(pre, preL, post, postL, n):
    if n == 0: return
    if n == 1:
        post[postL] = pre[preL]
        return
    m = (n - 1) / 2
    subtreeSize = m
    PreToPost(pre, preL + 1,     post, postL,     subtreeSize)
    PreToPost(pre, preL + 1 + m, post, postL + m, subtreeSize)
    post[postL + n - 1] = pre[preL]

复杂度

每个结点写入一次，时间 O(n)；递归栈空间 O(log n)，输出数组 O(n)。

边界条件

n=0 直接返回，n=1 只复制根。输入必须确为满二叉树，故 n=2^h-1；不满足时仅凭先序无法可靠划分子树。

易错点

不能把一般二叉树也按左右各一半切分；根必须最后写入当前后序片段，且右子树的下标偏移要加 m。

评分要点

利用左右 subtreeSize 相等；正确计算 m 和四个区间起点；根写在末尾；说明满二叉树前提。

设计一个算法，将二叉树的叶结点按从左到右的顺序连成单链表，表头指针为 head，并用叶结点的 right 指针域保存链表后继。

[tag_link]

参考答案

按先左后右的 DFS 次序遇到叶结点。head 记录首叶，tail 记录末叶；新叶到来时令 tail.right 指向它，结束后令最后一个叶结点的 right 为空。

伪代码

LinkLeaves(T, ref head, ref tail):
    if T == null: return
    if T.left == null and T.right == null:
        if head == null: head = T
        else: tail.right = T
        tail = T
        return
    LinkLeaves(T.left, head, tail)
    LinkLeaves(T.right, head, tail)

head = null; tail = null
LinkLeaves(root, head, tail)
if tail != null: tail.right = null

复杂度

每个结点访问一次，时间 O(n)；递归栈空间 O(h)，链表复用原指针，不另占结点空间。

边界条件

空树得到 head=null；单结点树中 head=tail=root 且 right=null；最后必须封尾。该做法会改写叶结点的 right 指针。

易错点

必须按左到右遍历；不要在处理完左子树前沿已改写的叶 right 再次递归，也不要忘记保存 tail 和封尾。

评分要点

正确识别叶结点；head/tail 初始化；按先左后右连接；tail.right = T；说明会破坏原树叶结点的 right 域。

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

[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；给出复杂度。