剑指 Offer 26. 树的子结构

题目地址(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 的一个子树拥有相同的结构和节点值。
示例 1：
输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：
0 <= 节点个数 <= 10000

前置知识

公司

• 暂无

思路

判断树 BB 是否是树 AA 的子结构，需完成以下两步工作

1. 先序遍历树 A 中的每个节点 nA ；（对应函数 isSubStructure(A, B)）
2. 判断树 AA中 以 nA 为根节点的子树 是否包含树 B 。（对应函数 recur(A, B)）

recur(A，B)函数:

1. 终止条件:
   1. 当节点B为空:说明树B已匹配完成(越过叶子节点)，因此返回true ;
   2. 当节点A为空:说明已经越过树A叶子节点，即匹配失败，返回false ;
   3. 当节点A和B的值不同:说明匹配失败，返回f alse ;
2. 返回值:
   1. 判断A和B的左子节点是否相等，即recur(A.left，B.left) ;
   2. 判断A和B的右子节点是否相等，即recur(A.right，B.right);

isSubStructure(A，B)函数:
1.特例处理:当树A为空或树B为空时，直接返回false ;
2.返回值:若树B是树A的子结构，则必满足以下三种情况之一，因此用或连接;

1. 以节点A为根节点的子树包含树B，对应recur(A，B);
2. 树B是树A左子树的子结构，对应isSubStructure(A.left，B);
3. 树B是树A右子树的子结构，对应isSubStructure(A.right，B);

关键点

代码

• 语言支持：Java

Java Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode a, TreeNode b) {
        //两颗树有一颗是空的就返回false
        if (a == null ||  b==null){
            return false;
        }
        //判断 两棵树的根节点比较是不是相等的 || a的左子树和b递归调用 || a的右子树和b递归调用 有一个是true就返回true
        return loop(a, b) || isSubStructure(a.left, b) || isSubStructure(a.right, b);
    }
    //判断ab为根节点的子树是不是相等的
    boolean loop(TreeNode a, TreeNode b){
        //b为空 说明b遍历完了 并且是a的子树 返回true
        if (b == null) {
            return true;
        }
        //a为空 说明b还没遍历完 b不是a的子树
        if (a == null) {
            return false;
        }
        //ab的值要是不相等的话也说明不是子树
        if (a.val != b.val) {
            return false;
        }
        //判断左右子树是否是相等的
        return loop(a.left, b.left) &&loop(a.right, b.right);
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：#card=math&code=O%28n%29&id=gkivx)
• 空间复杂度：#card=math&code=O%28n%29&id=jnXSO)