JZ17 树的子结构

描述

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

示例

输入：

{8,8,#,9,#,2,#,5},{8,9,#,2}

返回值：

true

解析

这题的思路还是比较明确的，树的问题基本都涉及到树的遍历，此处要遍历树 A，寻找与树 B 根节点相同的节点，从这个相同节点开始判断是否为子结构。

一开始写的代码为

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 == null)
            return false;
        // 遍历树 A 的同时判断节点是否相同
        return IsSubTree(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
    }
    
    // 判断是否为子树
    public boolean IsSubTree(TreeNode node1,TreeNode node2){
        // 若两个节点都为空，也是相同的
        if(node1 == null && node2 == null )
            return true;
        // 只有一个节点为空，说明肯定不一样
        if(node1 == null || node2 == null)
            return false;
        // 两节点不一样返回 false
        if(node1.val != node2.val )
            return false;
        // 递归判断左右子树
        return IsSubTree(node1.left,node2.left) && IsSubTree(node1.right,node2.right);
    }
    
}

提交结果为9/14 组用例通过，出现了问题

用例输出：

{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}

预期输出：

true

实际输出：

false

问题出在哪呢？看一看树 A 和树 B 的结构

可以发现，树 B 确实是 树 A 的子结构，但不是树 A 的子树！在判断到节点 2 的时候，树 A 的节点 2 有左右孩子 4 和 7，而树 B 的节点 2 没有左右孩子。上面的代码判断的是否为子树，所以产生了错误。

修改后的代码

/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if(root1 == null || root2 == null)
            return false;
        // 遍历树 A 的同时判断节点是否相同
        return IsSubTree(root1,root2) || HasSubtree(root1.left,root2) || HasSubtree(root1.right,root2);
    }
    
    // 判断是否为子结构
    public boolean IsSubTree(TreeNode node1,TreeNode node2){ 
        // 树 B 没有的节点，对树 A 不用做判断
        if( node2 == null )
            return true;
        // 树 B 有但树 A 没有的节点，说明不一样了
        if( node1 == null )
            return false;
        // 两节点不一样返回 false
        if(node1.val != node2.val )
            return false;
        // 递归判断左右子树
        return IsSubTree(node1.left,node2.left) && IsSubTree(node1.right,node2.right);
    }
}

用例全部通过！

总结

还是那句话：树的问题基本都会涉及树的遍历。在这题中要注意区分子树和子结构的概念！