题目描述
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
思路
Two Recursion:
- Find in Tree 1 if there is a tree node in Tree 1 equal to the root of Tree 2
- In this case, compare the every node in Tree 2 with Tree1, and then return the result.
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
|
/** 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){ if(root1.val == root2.val){ result = ifRoot1HasRoot2(root1,root2); } //find in left node if(!result){ result = HasSubtree(root1.left,root2); } //find in right node if(!result){ result = HasSubtree(root1.right,root2); } } return result; } public boolean ifRoot1HasRoot2(TreeNode root1,TreeNode root2){ boolean result = false; if(root2 == null){ result = true; } if(root1 != null && root2!= null){ if(root1.val == root2.val){ result = ifRoot1HasRoot2(root1.left,root2.left) &&ifRoot1HasRoot2(root1.right,root2.right); }else{ result = false; } } return result; } }
|
近期评论