26. 树的子结构

题目链接

Leetcode

题目描述

解题思路

分两步：

• isSubStructure 遍历 A 的每个节点，把它当作可能的起点，A 的根、左子树、右子树中任意一处匹配即可；
• isSubtreeWithRoot 从起点开始，同时向下比较两棵树：B 走到 null 说明 B 的这一支已经全部匹配，返回 true；A 走到 null 或值不同则返回 false。

B 为空树时，按题意不是任何树的子结构，直接返回 false。

public boolean isSubStructure(TreeNode A, TreeNode B) {
    if (A == null || B == null)
        return false;
    return isSubtreeWithRoot(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
}

private boolean isSubtreeWithRoot(TreeNode root1, TreeNode root2) {
    if (root2 == null)
        return true;
    if (root1 == null)
        return false;
    if (root1.val != root2.val)
        return false;
    return isSubtreeWithRoot(root1.left, root2.left) && isSubtreeWithRoot(root1.right, root2.right);
}