剑指Offer【树的子结构】

题目描述

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

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

例如:
给定的树 A:

给定的树 B：

1
2
3

  4 
 /
1

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

示例 1：

1 2	`输入：A = [1,2,3], B = [3,1] 输出：false`

示例 2：

1 2	`输入：A = [3,4,5,1,2], B = [4,1] 输出：true`

限制：

0 <= 节点个数 <= 10000

解法

先用先序遍历找到A中B的相等节点
再以这个节点为根节点开始判断两个树结构是否相等
如果结构不相等再继续寻找下一个相等节点

import leetcode.TreeNode;

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //特殊判断
        if (B == null) {
            return false;
        }
        //1.先序遍历搜索到A,B等值的节点
        return search(A, B);
    }

    /**
     * 在A里去找B.val==A.val
     * 找到相等的根节点的值
     * @param A
     * @param B
     * @return
     */
    public boolean search(TreeNode A, TreeNode B) {
        //1.定义递归出口
        if (A == null) {
            return false;
        }
        //2.比较是否值相等，且结构相等
        if (A.val == B.val && compare(A, B)) {
            return true;
        }
        //遍历左右子树
        return search(A.left, B) || search(A.right, B);

    }

    /**
     * 判断当前节点值是否相等
     * 判断左右子树是否相等
     *
     * @param A
     * @param B
     * @return
     */
    public boolean compare(TreeNode A, TreeNode B) {
        //1.定义递归出口
        if (B == null) {
            //B为空,A不为空，那B是A的子树。
            return true;
        }
        if (A == null) {
            //A空，B不空，必然不是子树
            return false;
        }
        return A.val == B.val && compare(A.left, B.left) && compare(A.right, B.right);
    }
}