def test_case3(self):
     nums = [6,5,8,1,3,7,11,None,None,None,None,None,None,9]
     answer = [6,3,8,1,5,7,11,None,None,None,None,None,None,9]
     root = TreeNode.generate_bt_from_list(nums)
     self.sol.recoverTree(root)
     compare = TreeNode.compare_tree(root, TreeNode.generate_bt_from_list(answer))
     self.assertTrue(compare)

 def test_case1(self):
     nums = [3,1,2]
     answer = [2,1,3]
     root = TreeNode.generate_bt_from_list(nums)
     self.sol.recoverTree(root)
     compare = TreeNode.compare_tree(root, TreeNode.generate_bt_from_list(answer))
     self.assertTrue(compare)

 def test_case2(self):
     nums = [1,2]
     root = TreeNode.generate_bt_from_list(nums)
     answer = [1,2]
     self.sol.flatten(root)
     result = TreeNode.get_tree_right_list(root)
     self.assertEqual(answer, result)

 def test_case1(self):
     preorder = "abc"
     inorder = "bac"
     answer = TreeNode("a")
     answer.left = TreeNode("b")
     answer.right = TreeNode("c")
     result = self.sol.buildTree(preorder, inorder)
     compare = TreeNode.compare_tree(answer, result)
     self.assertTrue(compare)

 def test_case11(self):  #===>
     nums = "98,97,#,88,#,84,#,79,87,64,#,#,#,63,69,62,#,#,#,30,#,27,59,9,#,#,#,3,#,0,#,-4,#,-16,#,-18,-7,-19,#,#,#,-23,#,-34,#,-42,#,-59,#,-63,#,-64,#,-69,#,-75,#,-81"
     answer = "98,#,97,#,88,#,84,#,79,#,64,#,63,#,62,#,30,#,27,#,9,#,3,#,0,#,-4,#,-16,#,-18,#,-19,#,-23,#,-34,#,-42,#,-59,#,-63,#,-64,#,-69,#,-75,#,-81,#,-7,#,59,#,69,#,87"
     from util.tree_node import TreeNode
     root = TreeNode.generate_bt_from_string_standard(nums)
     answer_tree = TreeNode.generate_bt_from_string_standard(answer)
     self.sol.flatten(root)
     compare = TreeNode.compare_tree(root, answer_tree)
     self.assertTrue(compare)

 def helper(self, left, right):
     if left>right:
         return None
     if left==right:
         return TreeNode(self.nums[left])
     mid = (left+right) / 2
     root = TreeNode(self.nums[mid])
     root.left = self.helper(left, mid-1)
     root.right = self.helper(mid+1, right)
     return root

 def gen_tree(self, nums, left, right):
     if left > right:
         return None
     if left == right:
         return TreeNode(nums[left])
     mid = left + int((right - left) / 2)
     root = TreeNode(nums[mid])
     root.left = self.gen_tree(nums, left, mid - 1)
     root.right = self.gen_tree(nums, mid + 1, right)
     return root

 def helper(self, preorder, inorder, l1, r1, l2, r2):
     if l1 > r1:
         return None
     root = TreeNode(preorder[l1])
     idx = l2
     while idx <= r2 and inorder[idx] != preorder[l1]:
         idx += 1
     lsize = idx - l2
     root.left = self.helper(preorder, inorder, l1 + 1, l1 + lsize, l2, idx)
     root.right = self.helper(preorder, inorder, l1 + lsize + 1, r1, idx + 1, r2)
     return root

 def build_max(self, A, start, end):
     if start > end:
         return None
     idx = start
     for i in range(start, end+1):
         if A[i] > A[idx]:
             idx = i
     root = TreeNode(A[idx])
     root.left = self.build_max(A, start, idx-1)
     root.right = self.build_max(A, idx+1, end)
     return root

 def generateBST(self, head, start, end):
     if start>end:
         return None
     mid = start + (end-start)/2
     left = self.generateBST(head, start, mid-1)
     root = TreeNode(head[0].val)
     head[0] = head[0].next
     right = self.generateBST(head, mid+1, end)
     root.left = left
     root.right = right
     return root

 def build_tree_rec(self, root_idx, in_left, in_right):
     if in_left > in_right:
         return None
     root = TreeNode(self.preorder[root_idx])
     if in_left == in_right:
         return root
     in_root = self.inorder.index(self.preorder[root_idx])
     left_length = in_root - in_left
     right_length = in_right - in_root
     root.left = self.build_tree_rec(root_idx+1, in_root-left_length, in_root-1)
     root.right = self.build_tree_rec(root_idx+1+left_length,in_root+1,in_right)
     return root

 def arr_to_tree(self, arr, left, right):
     if not arr:
         return None
     if left==right:
         return TreeNode(arr[left])
     if left>right:
         return None
     mid = (left+right)/2
     root = TreeNode(arr[mid])
     root.left = self.arr_to_tree(arr,left,mid-1)
     root.right = self.arr_to_tree(arr,mid+1,right)
     return root

 def maxTree(self, A): # ref, use stack to track the decreasing part
     if not A:
         return None
     stack = []
     for i in range(len(A)):
         cur = TreeNode(A[i])
         while stack and stack[-1].val < cur.val:  # if use if here, wrong for case 1
             cur.left = stack.pop()
         if stack:
             stack[-1].right = cur
         stack.append(cur)
     return stack[0]

 def helper(self, inorder, left, right, postorder, pl, pr):
     if left>right: #need this, otherwise wrong for case1
         return None
     if left == right:
         return TreeNode(inorder[left])
     root_val = postorder[pr]
     root = TreeNode(root_val)
     root_idx = inorder.index(root_val)
     right_len = right-root_idx
     root.left = self.helper(inorder, left, root_idx-1, postorder, pl, pr-right_len-1)
     root.right = self.helper(inorder, root_idx+1, right, postorder, pr-right_len, pr-1)
     return root

 def helper(self, head, tail):
     if head==tail:
         return None
     fast = head
     slow = head
     while fast.next != tail and fast.next.next!=tail:
         fast = fast.next.next
         slow = slow.next
     root = TreeNode(slow.val)
     root.left = self.helper(head, slow)
     root.right = self.helper(slow.next, tail)
     return root

 def to_bst(self, head, tail):
     if head is None or head==tail: # should move head==tail here, because tail is not included, otherwise wrong.
         return None
     elif head.next == tail:
         return TreeNode(head.val)
     fast = slow = head
     while fast != tail and fast.next!=tail:
         fast = fast.next.next
         slow = slow.next
     root = TreeNode(slow.val)
     root.left = self.to_bst(head, slow)
     root.right = self.to_bst(slow.next, tail)
     return root

        def helper(arr):
            if len(arr) == 0:
                return [None]
            ret = []
            for i in range(0, len(arr)):
                left = helper(arr[:i])
                right = helper(arr[i + 1:])

                for j in left:
                    for k in right:
                        dummy = TreeNode(arr[i])
                        dummy.left = j
                        dummy.right = k
                        ret.append(dummy)
            return ret

    def sortedListToBSTr(self, start, end):
        if start > end:
            return None

        # mid
        mid = (start + end) / 2

        left = self.sortedListToBSTr(start, mid - 1)
        root = TreeNode(Solution.h.val)
        Solution.h = Solution.h.next_node
        right = self.sortedListToBSTr(mid + 1, end)

        root.left = left
        root.right = right
        return root

    def dfs(self, start, end):
        if start > end: return [None]
        res = []
        for rootval in range(start, end+1):

            LeftTree = self.dfs(start, rootval-1)
            RightTree = self.dfs(rootval+1, end)
            for i in LeftTree:

                for j in RightTree:

                    root = TreeNode(rootval)
                    root.left = i
                    root.right = j
                    res.append(root)
        return res

 def test_case2(self):
     nums = [5, 3, 6, 2, 4, None, 7]
     target = 28
     root = TreeNode.generate_bt_from_list(nums)
     answer = False
     result = self.sol.findTarget(root, target)
     self.assertEqual(answer, result)