1.4 Tweaked Identical Binary Trees

 		 8a			 					8b			 								8
	 /		\	         /	      \		      	/	          \
	4				5	     	5	         4	        5						4
	/														\		           			/
	7														7		         				7

Input: TreeNode one, TreeNode two

Solution:

1. Case 1: 8a = 8b

Case 2: isTweaked(8a.left, 8b.left) && isTweaked(8a.right, 8b.right)

|| Case 3: isTweaked(8a.left, 8b.right) && isTweaked(8a.right, 8b.left)

2. Base case: one == null && two == null, return true;

one of them not null, return false;

one.key != two.key, return false;

TC: worst case checking both case 2 & 3, 4 + 4^1 + 4^2 +...+4^height+1 = 4^logn = O(n^2)

SC: at most having height of nodes in the stack = O(logn)

public boolean isTweaked(TreeNode one, TreeNode two) {
  if (one == null && two == null) { return true; }
  else if (one == null || two == null) { return false; }
  else if (one.key != two.key) { return false;}
  return isTweaked(one.left, two.left) && isTweaked(one.right, two.right)
    || isWeaked(one.left, two.right) && isTweaked(one.right, two.left);
}