你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

剑指Offer 26.树的子结构(二叉树、深度优先搜索)

2021-11-27 15:25:12

一、题目内容

        

二、题目分析

        这个问题主要有两个方面难以理解:如果B是A树中的一部分,那么B的头结点必然是A中的某一个节点,而B恰好是A中的那个节点的子部分。

        如上图示例2,B是A中以4为头结点的一部分,那么我们需要怎么做呢?很简单,挨个选取A中的节点并作为头结点,然后与B同时向下遍历,直到B遍历完,那么B就是A的一部分了。

        具体判断B是否为以某个节点开始的子部分的代码是:

 boolean ispart(TreeNode A,TreeNode B){
        if(B==null)
            return true;
        if(A==null||A.val!=B.val)
            return false;
        return ispart(A.left,B.left)&&ispart(A.right,B.right);
    }
    

         首先如果B为空,那么说明B子树已经正常遍历完毕,说明B是以A为头结点的树的子树。那么如果当前A为空B不为空或者当前A节点的值不等于B节点的值,很显然以A为头结点的子树不能完全包含B,所以应该返回false。如果现在AB节点的值相等而且B又还没有遍历完,那么我们就应该接着遍历了。

        在主函数中,我们首先要以判断以A为头结点的树是否包含B,是的话直接返回true,如果是否就在看看以A的左孩子节点和右孩子节点为头结点的树是否包含B。

        

 public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A!=null&&B!=null)&&(ispart(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B));
    }

三、完整代码

        

public boolean isSubStructure(TreeNode A, TreeNode B) {
        return (A!=null&&B!=null)&&(ispart(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B));
    }
    boolean ispart(TreeNode A,TreeNode B){
        if(B==null)
            return true;
        if(A==null||A.val!=B.val)
            return false;
        return ispart(A.left,B.left)&&ispart(A.right,B.right);
    }