剑指 Offer 26. 树的子结构

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

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

例如:
给定的树 A:

给定的树 B：

1
2
3

  4 
 /
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的子树，我们将这个问题分为两部分：

树A的根节点记作A;
树B的根节点记作B;
1.在A树中找一个节点与B树根节点相同（前序遍历模板）
2.对比后续的节点（前序遍历模板）

代码

public class Solution {
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        //两个二叉树有一个为空则直接返回false
        if(root1==null||root2==null) return false;
        return recur(root1,root2) || HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
    }
    boolean recur(TreeNode a,TreeNode b){
        // b为空，就是完成了对B这个二叉树的遍历，就是找完了返回true
        if(b==null) return true;
        // a为空说明越过a树的叶子结点，没匹配完，所以返回false
        if(a==null) return false;
        // a和b的节点值不相等，返回false
        if(b.val!=a.val) return false;
        // 同时前序遍历a和b这两个树，递归匹配节点
        return recur(a.left,b.left) && recur(a.right,b.right);
    }
}

shubo的博客

判断树的子结构

剑指 Offer 26. 树的子结构

思路

代码