Advertisement
Guest User

task5 (updated)

a guest
Aug 25th, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.03 KB | None | 0 0
  1. class Solution {
  2.     public boolean isSubtree(TreeNode s, TreeNode t) {
  3.         int heightT = findHeight(t);
  4.         return isSubTree(s, t, heightT);
  5.     }
  6.    
  7.     private boolean isSubTree(TreeNode s, TreeNode t, int heightT) {
  8.         int curHeightS = findHeight(s);
  9.         if (s == null || curHeightS < heightT) {
  10.             return false;
  11.         }
  12.         if (curHeightS == heightT) {
  13.             return isEquals(s, t);
  14.         }
  15.         return isSubTree(s.left, t, heightT) || isSubTree(s.right, t, heightT);
  16.     }
  17.    
  18.     private boolean isEquals(TreeNode s, TreeNode t) {
  19.         if (s == null && t == null) {
  20.             return true;
  21.         }
  22.         if (s == null || t == null) {
  23.             return false;
  24.         }
  25.         return s.val == t.val && isEquals(s.left, t.left) && isEquals(s.right, t.right);
  26.     }
  27.    
  28.     private int findHeight(TreeNode node) {
  29.         if (node == null) {
  30.             return -1;
  31.         }
  32.         return Math.max(findHeight(node.left), findHeight(node.right)) + 1;
  33.     }
  34. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement