【题26 树的子结构】

Dear 丶 2022-03-25 09:52 114阅读 0赞

**【题26 树的子结构】**  
**【题目】**  
输入两棵二叉树A和B判断B是不是A的子结构。  
**例如：**  
如图两棵二叉树，由于A中有一部分子树的结构和B是一样的，因此B是A的子结构  
![在这里插入图片描述][20190120094347441.png]  
要查找树A中是否存在和树B结构一样的子树。分2步  
第一步，在树A中找到和树B的根节点的值一样的节点R；  
第二步，判断树A中以R为根节点的子树是不是包含和树B一样的结构。  
**例，**  
（1）首先在A中找到值为8（树B的根节点的值）的节点，从树中的根节点开始遍历（遍历/回归），发现根节点值就是8，判断树A的根节点下面的子树是不是含有和树B一样的结构，如图，在A中，根节点的左子节点的值为8，而树B的根节点的左子节点是9，对应的两个节点不同。  
![在这里插入图片描述][20190120094500856.png]  
![在这里插入图片描述][201901200945109.png]  
（2）仍然需要遍历树A，查找值为8的节点，第二层找到了一个值为8的节点，进行第二步判断，即，判断这个节点下面的子树是否含有和树B一样的结构，如图，于是遍历这个节点下面的子树，先后得到2个节点9和2和树B结构完全相同。![在这里插入图片描述][20190120094522292.png]  
![在这里插入图片描述][20190120094530522.png]  
面试时，要注意\*\*边界条件检查，\*\*即检查空指针，当树A或树B为空时，定义相应输出，第二步也是递归判断  
测试用例，  
树A和树B的头节点有一个或者2个都是空指针；  
在树A和树B中所有节点都只有左子节点或右子节点；  
树A和树B的节点中含有分叉。

**注：**  
由于计算机表示小数（包括float和double型小数）都有误差，我们不能直接调用等号（=），判断两个小数是否相等，如果2个小数的差的绝对值很小，如小于0.0000001，就认为它们相等。

**实现**

**小结：**  
3方面写出高质量的代码，**规范性，完整性，鲁棒性**  
**考虑所有可能的输入，完成基本功能，考虑边界条件，做好错误处理**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]  
**实现**

/**
    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(root2 == null){ //如果树2是空树，不是子树
                return false;
            }
            if(root1 == null && root2!= null){//如果1树是空树，2树不是空树 不是子树
                return false;
            }
            boolean result = false;
            if(root1.val == root2.val){//如果两个树根节点值相等
                result = hasSubTree(root1,root2);//进入hasSubTree函数
            }
            if(!result){//如果根节点不相等，看1树的根节点的左子树与2是不是相同
                result = HasSubtree(root1.left,root2);
                if(!result){//如果根节点不相等，看1树的根节点的右子树与2是不是相同
                    result = HasSubtree(root1.right,root2);
                }
            }
            return result;
        }
        
        private boolean hasSubTree(TreeNode root1,TreeNode root2){
            if(root2 == null){
                return true;
            }
            if(root1 == null && root2!= null ){
                return false;
            }
            if(root1.val == root2.val){//如果两个数当前节点值相等，看它的左子树和右子树是不是相同
                return hasSubTree(root1.left,root2.left)&&hasSubTree(root1.right,root2.right);
            }else{
                return false;
            }
        }
    }

[20190120094347441.png]: /images/20220325/e3af68476c41401894cf76e79f0da4a2.png
[20190120094500856.png]: /images/20220325/8b85eaf1309c4b98969aa55e17d78675.png
[201901200945109.png]: /images/20220325/6ee66b947cd44802a2bc16398a970931.png
[20190120094522292.png]: /images/20220325/ca215b67186a43a3a10d988d53aac7a1.png
[20190120094530522.png]: /images/20220325/e163bd31e2214dd0aea40cf48d0b89a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5NTA0OQ_size_16_color_FFFFFF_t_70]: /images/20220325/4398107894794b2aa72572fda9a1dc21.png