Advertisement
Byleth_CYY

Tweaked identical binary tree

Apr 6th, 2020
352
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.63 KB | None | 0 0
  1. """
  2. Definition of TreeNode:
  3. class TreeNode:
  4.    def __init__(self, val):
  5.        self.val = val
  6.        self.left, self.right = None, None
  7. """
  8.  
  9. class Solution:
  10.     """
  11.    @param a: the root of binary tree a.
  12.    @param b: the root of binary tree b.
  13.    @return: true if they are tweaked identical, or false.
  14.    """
  15.     def isTweakedIdentical(self, a, b):
  16.         if not a and not b:
  17.             return True
  18.        
  19.         if a and not b:
  20.             return False
  21.        
  22.         if b and not a:
  23.             return False
  24.         # write your code her
  25.    
  26.         def inorder_traversal_left(root,res):
  27.             if not root:
  28.                 return
  29.            
  30.             inorder_traversal_left(root.left,res)
  31.             res.append(root.val)
  32.             inorder_traversal_left(root.right,res)
  33.             return
  34.        
  35.         def inorder_traversal_right(root,res):
  36.             if not root:
  37.                 return
  38.            
  39.             inorder_traversal_right(root.right,res)
  40.             res.append(root.val)
  41.             inorder_traversal_right(root.left,res)
  42.             return
  43.        
  44.         def preorder(root,res):
  45.             if not root:
  46.                 return
  47.            
  48.             res.append(root.val)
  49.             preorder(root.left,res)
  50.             preorder(root.right,res)
  51.             return
  52.        
  53.         def same_tweaked_tree(x,y):
  54.             if not x and not y:
  55.                 return True
  56.            
  57.             if x and not y:
  58.                 return False
  59.            
  60.             if y and not x:
  61.                 return False
  62.            
  63.             return same_tweaked_tree(x.left,y.right) and same_tweaked_tree(x.right,y.left)
  64.  
  65.         a_inorder_left=[]
  66.         b_inorder_left,b_inorder_right=[],[]
  67.        
  68.         inorder_traversal_left(a,a_inorder_left)
  69.         inorder_traversal_left(b,b_inorder_left)
  70.         inorder_traversal_right(b,b_inorder_right)
  71.        
  72.         tweaked=False
  73.         print(a_inorder_left)
  74.         print(b_inorder_left)
  75.         print(b_inorder_right)
  76.        
  77.         if a_inorder_left==b_inorder_left:
  78.             return True
  79.         else:
  80.             if a_inorder_left==b_inorder_right:
  81.                 tweaked=True
  82.             else:
  83.                 return False
  84.        
  85.         print(tweaked)
  86.         if not tweaked:
  87.             a_preorder,b_preorder=[],[]
  88.             preorder(a,a_preorder)
  89.             preorder(b,b_preorder)
  90.             return a_preorder==b_preorder
  91.         else:
  92.             print('here')
  93.             return same_tweaked_tree(a,b)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement