力扣剑指offer26

面试题26

树的子结构

(先序遍历+递归)


题目:

https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:

-
给定的树 A:



    3

    / \

   4   5

  / \

 1   2



-
给定的树 B：



   4 

  /

 1




返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。


解题思路


解题图片


若树 B 是树 A 的子结构，则子结构的根节点可能为树 A 的任意一个节点。因此，判断树 B 是否是树 AA 的子结构，需完成以下两步工作：

  1. 先序遍历树 AA 中的每个节点 n_A；

    对应函数 isSubStructure(A, B)

  1. 判断树 A 中 以 n_A为根节点的子树 是否包含树 B。
    对应函数 recur(A, B)

代码


1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution {

    public boolean isSubStructure(TreeNode A, TreeNode B) {
        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);
    }
}