SHOW:
|
|
- or go back to the newest paste.
| 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) |
