树的子结构

川长思鸟来 2022-05-24 22:06 258阅读 0赞

![这里写图片描述][70]

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;
            }
            boolean result=false;
            if(root1!=null&&root2!=null)
            {
                 //从根的位置寻找
                 if(root1.val==root2.val)
                 {
                        result=isSame(root1,root2);
                 }
                 //根的位置没找到，在左子树位置上找
                 if(!result)
                 {
    
                       result=isSame(root1.left,root2);
                 }
                 //左子树没找到，在右子树位置上找
                 if(!result)
                 {
                       result=isSame(root1.right,root2);
                 }
    
    
            }
    
            return result;
        }
    
        //递归的思想求解一棵二叉树是否是另一颗二叉树的子树
        public boolean isSame(TreeNode node1,TreeNode node2){
    
            if(node2==null){
                return true;
            }
            if(node1==null)
            {
               return false;
            }
            if(node1.val!=node2.val)
            {  
    
                return false;   
    
            }
    
            return isSame(node1.left,node2.left)&&isSame(node1.right,node2.right);
        }
    
        public static void main(String[]args){
    
              TreeNode root1=new TreeNode(1);
              root1.left=new TreeNode(2);
              root1.right=new TreeNode(3);
              root1.left.left=new TreeNode(4);
              root1.left.right=new TreeNode(5);
    
              TreeNode root2=new TreeNode(2);
              root2.left=new TreeNode(4);
              root2.right=new TreeNode(5);
              Solution s=new Solution();
              System.out.println(s.HasSubtree(root1,root2));
        }
    }

![这里写图片描述][70 1]

[70]: /images/20220525/a506c10f3b7c487c9a16f0b191fdd664.png
[70 1]: /images/20220525/b93072559ee942d9962a09b6f98eb64f.png