Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public boolean isSubtree(TreeNode s, TreeNode t) {
- int heightT = findHeight(t);
- return isSubTree(s, t, heightT);
- }
- private boolean isSubTree(TreeNode s, TreeNode t, int heightT) {
- int curHeightS = findHeight(s);
- if (s == null || curHeightS < heightT) {
- return false;
- }
- if (curHeightS == heightT) {
- return isEquals(s, t);
- }
- return isSubTree(s.left, t, heightT) || isSubTree(s.right, t, heightT);
- }
- private boolean isEquals(TreeNode s, TreeNode t) {
- if (s == null && t == null) {
- return true;
- }
- if (s == null || t == null) {
- return false;
- }
- return s.val == t.val && isEquals(s.left, t.left) && isEquals(s.right, t.right);
- }
- private int findHeight(TreeNode node) {
- if (node == null) {
- return -1;
- }
- return Math.max(findHeight(node.left), findHeight(node.right)) + 1;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement