剑指Offer-面试题26-树的子结构

2020-05-04

题目描述

输入两棵二叉树 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

思路

使用递归对两颗树的节点进行比较判断。

代码

/**
 * 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){
        //若A、B是空树，则返回false，因为约定空树不是任意一个树的子结构
        if(A==null || B==null){
            return false;
        }
        //如果当前根节点相同，则以当前根节点的树进行比较
        if(A.val == B.val){
            if(judge(A,B)){
                return true;
            }
        }
        //如果当前根节点不相同，则比较A的左节点为根节点的树或右节点为根节点的树
        return isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }
    //判断两颗树是否有相同结构
    public boolean judge(TreeNode root,TreeNode sub){
        if(sub == null){    //如果sub到了null，证明sub是root的子树
            return true;
        }   //如果root到了null，证明sub还没比较完，说明不是子树
        if(root == null){
            return false;
        }   //如果两节点值相同，则继续比较root和sub的左节点，root和sub的右节点
        if(root.val == sub.val){
            return judge(root.left,sub.left) && judge(root.right,sub.right);
        }   //节点值不相同，则返回false
        return false;
    }
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。