问题

剑指 Offer 26. 树的子结构
难度中等70
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。
例如:
给定的树 A:

  1.      3
  2.     / \
  3.    4   5
  4.   / \
  5.  1   2

给定的树 B：

  1.    4 
  2.   /
  3.  1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：
0 <= 节点个数 <= 10000

解答

若 B 是 A 的子树，则B 中的根节点可能是 A 中的任意节点，因此，判断 B 是否是 A 的子结构，则需要进行以下判断：
以 A 的任意节点 An 为 B 的根节点：遍历 A 树，判断以任意节点 An 的子树，是否包含 B。
利用先序遍历 A 树，每次遍历，判断，以当前节点为根节点的子树是否与 B 相同：
递归调用 isSameTree(TreeNode root，TreeNode B)：
返回值：

  1.   - 当 B == null，说明 B 树越过叶子节点，匹配完成，返回 true。
  2.   - 当 root == null，root 越过叶子节点，匹配失败，返回 false。
  3.   - 当 root.val  != B.val，两颗树的节点不相同，匹配失败，返回 false
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
       if(A == null ||  B == null) return false;
       Deque<TreeNode> stack = new ArrayDeque<>();
       stack.push(A);
       // 先序遍历 A 树
       while(!stack.isEmpty()){
            TreeNode  root = stack.pop();
            // 判断以当前节点的子树是否等于 B 
            if(isSameTree(root,B)) return true;
            if(root.right != null)
                stack.push(root.right);
            if(root.left != null)
                stack.push(root.left);
       }
       return false;
    }
    // 判断两个子树是否相同
    private boolean isSameTree(TreeNode root, TreeNode sub){
        // 如果 B 为 null，说明越过叶子节点，返回true 
        if(sub == null) return true;
        // root 为 null 或者子节点的值不相同，说明两个树不同，匹配失败
        if(root == null || root.val != sub.val) return false;
        return isSameTree(root.left, sub.left) && isSameTree(root.right, sub.right);
    }

}

执行结果：通过
显示详情
执行用时：7 ms, 在所有 Java 提交中击败了5.66%的用户
内存消耗：41.4 MB, 在所有 Java 提交中击败了100.00%的用户

大佬的解答：

大佬的解答
利用递归先序遍历 A 树，然后再以 A 树中的任意节点为根节点的子树，与 B 树进行判断，判断是否是相同的

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 前序遍历的同时，以 A 的每个节点为 B 的 root 节点，判断 B 是否是 A 的子树
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }
    boolean recur(TreeNode A, TreeNode B) {
        if(B == null) return true;
        if(A == null || A.val != B.val) return false;
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

执行结果：通过
显示详情
执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41.3 MB, 在所有 Java 提交中击败了100.00%的用户