【树2】树的子结构

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构。） /** 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) { boolean result=false; if(root1!=null && root2!=null){ //A，B树当前结点相同的话，就继续比较A,B数下个结点 if(root1.val==root2.val) result=DoesRoot1HaveRoot2(root1,root2); //A，B树当前结点不相同的话，就继续比较A左结点与B树当前结点 if(!result) result=HasSubtree(root1.left,root2); //A左结点与B树当前结点不相同的话，就继续比较A右结点与B树当前结点 if(!result) result=HasSubtree(root1.right,root2); } return result; } /** *A，B树当前结点相同的前提下，继续比较A,B树下个结点 * / private boolean DoesRoot1HaveRoot2(TreeNode root1,TreeNode root2) { if(root2==null) return true; if(root1==null) return false; if(root1.val!=root2.val) return false; return DoesRoot1HaveRoot2(root1.left,root2.left) &&DoesRoot1HaveRoot2(root1.right,root2.right); } }