笔试面试算法经典--二叉树的子结构（Java）

题目描述 输入两棵二叉树A，B，判断B是不是A的子结构（空树不是任意一个树的子结构）。下图中：右边的二叉树是左边二叉树的子结构

解法： 先序遍历 A树，如果当前节点与 B树的根节点相同，则判断 B 是不是 A的子树，判断 B是 A 的子树的也用递归：比较 B 的左子树 是否是 A 左子树的子结构，B 的右子树是否是 A的右子树的子结构。因此需要两个函数来进行，一个函数来进行先序遍历，一个来判断是否是子树。

---

/* class TreeNode{ int val; TreeNode left=null; TreeNode right=null; public TreeNode(int val) { this.val = val; } } */ public static boolean hasSubtree(TreeNode root1,TreeNode root2) { if((root1==null)||(root2==null)) return false; //A B 都是null 时返回FALSE，此时已经遍历到了叶子节点，且不存在相同的节点。 boolean result=false; //如果A中节点与B的头节点相同，则判断B是不是A的子树。如果不是，则看A的左子树是不是，否则看A的右子树。 if(root1.val==root2.val) { result=IsSubTree(root1,root2); } if(!result) { result=hasSubtree(root1.left, root2); } if(!result) { result=hasSubtree(root1.right, root2); } return result; } //判断B是不是A的子结构。 public static boolean IsSubTree(TreeNode root1,TreeNode root2) { if(root2==null) return true; if(root1==null) return false; if(root1.val==root2.val) return IsSubTree(root1.left, root2.left)&&IsSubTree(root1.right, root2.right); else { return false; } }