LeetCode 练习——剑指 Offer 26. 树的子结构

1.题目描述

剑指 Offer 26. 树的子结构
输入两棵二叉树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

2.解题思路与代码

2.1 解题思路

题目要求判断 B 是否为 A 的子树，那么首先我们就需要在 A 中找到 B 的根结点，然后从根节点开始以此判断节点是否相同。因此题目就变成了两个步骤：在 A 中寻找 B 的根结点相同的节点、以该节点为根结点和 B 依次比较判断是否相同。以题目示例 2 进行图解。
首先在 A 中寻找和 B 根结点值相同的点

在 A 中找到节点以后，以该节点为根结点与 B 从根节点开始进行比较，直到 B 遍历完成

需要注意的是，题目中节点的值可能相同，因此需要对 A 每个节点进行查找，并且每查找到一个就进行一次比较。

2.2 代码

class Solution {
    
    boolean ans = false;

    public boolean isSubStructure(TreeNode A, TreeNode B) {
    
        if (B == null) {
    
            return false;
        }
        find(A, B);
        return ans;
    }
	// 比较两个树是否相同
    public boolean compare(TreeNode root, TreeNode compareNode) {
    
        if (root == null) {
    
            return compareNode == null;
        }
        if (compareNode == null) {
    
            return true;
        }
        if (root.val != compareNode.val) {
    
            return false;
        }
        // 比较当前节点的最左子树
        boolean p1 = compare(root.left, compareNode.left);
        // 比较当前节点的右子树
        boolean p2 = compare(root.right, compareNode.right);
        return p1 & p2;
    }

    public void find(TreeNode root, TreeNode compareNode) {
    
        if (root == null) {
    
            return;
        }
        if (root.val == compareNode.val) {
    
        	// 当前节点的值与进行比较的树头节点值相同时，进行比较
            boolean compare = compare(root, compareNode);
            ans |= compare;
        }
        // 查找左子树
        find(root.left, compareNode);
        // 查找右子树
        find(root.right, compareNode);
    }
}

2.3 测试结果

通过测试

3.总结

• 按照题目要求需要对树进行查找和比较两个过程
• 每查找到一次相同值节点就需要进行一次比较