拓者设计吧官方网站,网站常用字体大小,外贸平台推广,网站销售怎么做题目描述输入两棵二叉树 A、B#xff0c;判断 B 是不是 A 的子结构。 我们规定空树不是任何树的子结构。 样例 树 A#xff1a; 8 / \ 8 7 / \ 9 2 / \ 4 7 树 B#xff1a; 8 / \ 9 2 返回 true ,因为 B 是 A 的子结构。 解法递归方式遍历#xff1a; 在树 A 中找到和树 B…题目描述输入两棵二叉树 A、B判断 B 是不是 A 的子结构。 我们规定空树不是任何树的子结构。 样例 树 A 8 / \ 8 7 / \ 9 2 / \ 4 7 树 B 8 / \ 9 2 返回 true ,因为 B 是 A 的子结构。 解法递归方式遍历 在树 A 中找到和树 B 的根结点值一样的结点 R判断树 A 以 R 为根结点的子树是否包含与树 B 一样的结构。 package demo;public class Solution {//Definition for a binary tree node.public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val x; }}public static boolean hasSubTree(TreeNode pRoot1, TreeNode pRoot2){boolean res false;if(pRoot1 ! null pRoot2 ! null){if(pRoot1.val pRoot2.val){res isSame(pRoot1, pRoot2);}if(!res){//resfalseres hasSubTree(pRoot1.left, pRoot2);}if(!res){res hasSubTree(pRoot1.right, pRoot2);}}return res;}private static boolean isSame(TreeNode root1, TreeNode root2) {if(root2null){return true;}if(root1null || root1.val !root2.val){return false;}return isSame(root1.left, root2.left) isSame(root1.right, root2.right);}public static void main(String[] args) {TreeNode R1 new TreeNode(8); TreeNode n2 new TreeNode(8); R1.left n2; TreeNode n3 new TreeNode(7); R1.right n3;TreeNode n4 new TreeNode(9); n2.left n4;TreeNode n5 new TreeNode(2); n2.right n5;TreeNode n6 new TreeNode(4); n5.left n6;TreeNode n7 new TreeNode(7); n5.right n7;TreeNode R2 new TreeNode(8); TreeNode ns2 new TreeNode(9); R2.leftns2;TreeNode ns3 new TreeNode(2); R2.rightns3;boolean t hasSubTree(R1, R2);System.out.println(t);}
} 转载于:https://www.cnblogs.com/lisen10/p/11183392.html
