剑指OfferJZ17：树的子结构-java版

短命女 2022-10-13 12:52 5阅读 0赞

### 剑指OfferJZ17：树的子结构-java版 ###

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

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]

**思路：**  
**1.查找**：首先将二叉树B的根节点与二叉树A的每一个节点比较  
如果在二叉树A中找到与二叉树B根节点一致的节点node  
**2.匹配**：那么就在二叉树A中抽离出以node节点为根节点的子树，与二叉树B进行比较

我们选择**前序遍历**：根据前序遍历特点–中左右，每次都从树的root节点开始遍历，符合题意

public class jz17 { 
        //匹配
        private boolean judge(TreeNode node1,TreeNode node2){ //node1二叉树A的节点 node2二叉树B的节点
            if(node2==null){ 
                return true;//说明在某个方向中二叉树A中有二叉树B的节点
            }
            if (node1 == null) { 
                return false;//说明在某个方向上二叉树A中没有二叉树B的节点
            }
            if(node1.val== node2.val){ 
                boolean flag1=true;//默认左子树是匹配的
                boolean flag2=true;//默认右子树是匹配的
                if(node1.left!=null || node2.left!=null){ 
                    flag1=judge(node1.left,node2.left);
                }
                if(flag1 && (node1.right!=null || node2.right!=null)){ //flag1：减枝 flag1：如果左边匹配成功1，才能进行右边的比较
                    flag2=judge(node1.right,node2.right);
                }
                return flag1 && flag2;//需要一个节点的左右子树都匹配成功
            }else { 
                return false;
            }
        }
    
        //使用前序遍历---查找
        private boolean dfs(TreeNode node,TreeNode root2){ //node：二叉树A的节点 root2：二叉树B的根节点
            boolean flag=false;
            if(node.val==root2.val){ //在二叉树A中找到与二叉树B根节点相同的节点
                //进入二叉树的匹配（比较）过程
                flag=judge(node, root2);
            }
            if(flag){ 
                return true;//通过当前节点已经找到二叉树的完全匹配结果了，不用再往下遍历二叉树了（也是减枝的一个过程）
            }
            boolean flag1=false;//用来记录当前节点的左子树中的查找结果（比较过程）
            boolean flag2=false;//用来记录当前节点的右子树中的查找结果（比较过程）
            if(node.left!=null){ 
                flag1=dfs(node.left,root2);
            }
            if((!flag1) && node.right!=null){ //!flag1是一个减枝的过程（之前遍历过的不再遍历）
                flag2=dfs(node.right,root2);
            }
            return flag1 || flag2;//只要找到节点的某一个方向（左子树或右子树）进行匹配成功就行了
        }
        public boolean HasSubtree(TreeNode root1,TreeNode root2) { 
            if (root1 == null || root2 == null) { //二叉树A是一颗空树 或二叉树B是一颗空树
                return false;
            }
    
            return dfs(root1,root2);
    
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20210707104927909.gif_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]: /images/20221005/205dddaef38f400db55c38901c6550a2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]: /images/20221005/8f92d5146917425e9f02cf4daefe9c8d.png
[20210707104927909.gif_pic_center]: /images/20221005/0a42c52fad4e4c6aaa187eef87c50d8d.png