树的子结构

发表于 | 更新于 | 分类于 | 阅读次数： | 阅读次数：
本文字数： 1.4k | 阅读时长 ≈ 2 分钟

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）。


代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public static boolean HasSubtree(TreeNode root1, TreeNode root2) {
        boolean result = false;
        //当两树都不为null的时候，才进行比较。否则直接返回false
        if (root2 != null && root1 != null) {
            //如果两树的当前根节点值相等
            if(root1.val == root2.val)
                //就判断以root1为根节点的Tree1是否包含（或相等）Tree2
                result = doesTree1HaveTree2(root1,root2);
            //如果不包含，向左递归
            if (!result)
                result = HasSubtree(root1.left,root2);
            //如果不包含，向右递归
            if (!result)
                result = HasSubtree(root1.right,root2);
        }
            //返回查找结果
            return result;
    }

// Tree1以node1为起点，Tree2以node2为起点，分别开始向下进行匹配。判断Tree1是否包含（或相等）Tree2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    public static boolean doesTree1HaveTree2(TreeNode node1, TreeNode node2) {
        //如果Tree2已经遍历完了且都能对应的上Tree1，返回true
        if (node2 == null)
            return true;
        else if(node1 == null)
            //如果Tree2还没有遍历完，Tree1却遍历完了（说明Tree2比Tree1大），返回false
            return false;

        //如果其中有一个点没有对应上，就返回false
        if (node1.val != node2.val)   
                return false;
        else
            //如果根节点对应的上，那么就分别再去匹配左右子结点的值，看是否也能对应的上。（左比左，右比右）
            return doesTree1HaveTree2(node1.left,node2.left) && doesTree1HaveTree2(node1.right,node2.right);
    }
}

---------------- The End ----------------
0%