树的子结构

问题陈述

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
例如:
给定的树 A:

​        3
​       / \
​      4   5
​     / \
     1   2
给定的树 B：

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

思路分析

  • 判断A，B是否为空，
  • 比较A，B的头结点是否相等，若不等，继续比较A的左子结点，右子结点是否与B相等。
  • 使用dfs进行深度查找，如果B为空了，说明匹配成功；如果A为空或者A！=B，匹配失败；
  • 继续深度遍历A和B的左右子结点。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class SubStructrue_Of_Tree {
    public boolean isSubTree(TreeNode A,TreeNode B){
        if(A==null||B==null) return false; //判断A，B是否为空，
        return dfs(A,B)||isSubTree(A.left,B)||isSubTree(A.right,B);//比较A，B的头结点是否相等，若不等，继续比较A的左子结点，右子结点是否与B相等。
    }
    public boolean dfs(TreeNode A,TreeNode B){
        if(B==null) return true;    //先判断B是否为空，B空意味着匹配完成。
        if(A==null||A.val!=B.val) return false;   //若B不空，A为空或者A，B不等，匹配失败。
        return dfs(A.left,B.left)&&dfs(A.right,B.right);  //A，B都不空，继续判断A，B的左结点和右结点。
    }
    public static void main(String[] args){
        TreeNode A=new TreeNode(4);
        A.left=new TreeNode(3);
        A.right=new TreeNode(7);
        A.right.right=new TreeNode(3);
        TreeNode B=new TreeNode(7);
        B.right=new TreeNode(3);
        SubStructrue_Of_Tree subStructrue_of_tree=new SubStructrue_Of_Tree();
        System.out.println(subStructrue_of_tree.isSubTree(A,B));
    }
}