PYTHON_STUDY DFS and divide and conquer

1 Iteration on tree:(preorder is the inverse of postorder)
Inorder traversal:
def inorderTraversal(self, root):
        # write your code here
        state_stack, result, current = [], [], root
        while True:
            while current is not None:
                state_stack.append(current)
                current = current.left
            if len(state_stack) == 0:
                break
            node = state_stack.pop()
            if node is not None:
                result.append(node.val)
            current = node.right
        return result
        
Preorder traversal:
def preorderTraversal(self, root):
        # write your code here
        state_stack, result, current = [], [], root
        while True:
            while current is not None:
                state_stack.append(current)
                result.append(current.val)
                current = current.left
            if len(state_stack) == 0:
                break
            node = state_stack.pop()
            current = node.right
        return result
        
postorder traversal:
def postorderTraversal(self, root):
        # write your code here
        first_state_stack, sec_state_stack = [root], []
        while len(first_state_stack) > 0:
            node = first_state_stack.pop()
            if node is not None:
                sec_state_stack.insert(0,node.val)
                first_state_stack.append(node.left)
                first_state_stack.append(node.right)
        return sec_state_stack
        
divide and conquer example problem: check validate binary search tree
def __init__(self):
        self.lastnode, self.result = None, True
        
    def traversal(self, root):
        if root is not None:
            self.traversal(root.left)
            if self.lastnode is not None and self.lastnode.val >= root.val:
                self.result = False
            self.lastnode = root
            self.traversal(root.right)
        
    #return maximum val of subtree rooted by root; minimum val of subtree rooted by root; boolean indicating if subtree rooted by root is a valida binary search tree
    def divide_conquer(self, root):
        if root is None:
            return 0-math.inf, math.inf, True
        leftmax, leftmin, is_bst_left = self.divide_conquer(root.left)
        rightmax, rightmin, is_bst_right = self.divide_conquer(root.right)
        if is_bst_left == False or is_bst_right == False:
            return None, None, False
        if leftmax >= root.val or rightmin <= root.val:
            return None, None, False
        else:
            return max(rightmax, root.val), min(leftmin, root.val), True
        
    """
    @param root: The root of binary tree.
    @return: True if the binary tree is BST, or false
    """
    def isValidBST(self, root):
        # write your code here
        #self.traversal(root)
        #return self.result
        maxval, minval, result = self.divide_conquer(root)
        return result
        
problem: binary tree path sum using divide and conquer:
Your are given a binary tree in which each node contains a value. Design an algorithm to get all paths which sum to a given value.
The path does not need to start or end at the root or a leaf, but it must go in a straight line down.
def divide_conquer(self, root, target):
        if root is None:
            return []
        leftpath = self.divide_conquer(root.left, target)
        rightpath = self.divide_conquer(root.right, target)
        newpath = leftpath + rightpath
        result = []
        if root.val == target:
            self.result.append([root.val])
        result.append([root.val])
        for i in range(len(newpath)):
            sumpath = sum(newpath[i])
            if root.val + sumpath == target:
                self.result.append([root.val]+newpath[i])
            result.append([root.val]+newpath[i])
        return result
        
Follow up of binary tree path sum III: any path in the binary tree is now possible !(left->root->right/left->root/root->right)
def divide_conquer(self, root, target):
        if root is None:
            return []
        leftpath = self.divide_conquer(root.left, target)
        rightpath = self.divide_conquer(root.right, target)
        result = []
        
        if root.val == target:
            self.result.append([root.val])
        result.append([root.val])
        
        for l_path in leftpath:
            lreverse_path = l_path[::-1]
            sumleft = sum(l_path)
            if sumleft + root.val == target:
                self.result.append(l_path + [root.val])
                self.result.append([root.val] + lreverse_path)
            result.append(l_path + [root.val])
            for r_path in rightpath:
                rreverse_path = r_path[::-1]
                sumright = sum(r_path)
                if sumleft + sumright + root.val == target:
                    self.result.append(l_path + [root.val] + rreverse_path)
                    self.result.append(r_path + [root.val] + lreverse_path)
        
        for r_path in rightpath:
            rreverse_path = r_path[::-1]
            sumright = sum(r_path)
            if sumright + root.val == target:
                self.result.append(r_path + [root.val])
                self.result.append([root.val] + rreverse_path)
            result.append(r_path + [root.val])
                    
        return result

sample code for finding successor and predecessor in the binary search tree:
def find_next_node(self, currentnode, root):
        if currentnode is None or (currentnode.right is None and currentnode == root):
            return None
        if currentnode.right:
            temp = currentnode.right
            while temp.left:
                temp = temp.left
            return temp
        else:
            temp, lastnode = root, None
            while temp is not None and temp != currentnode:
                if temp.val > currentnode.val:
                    lastnode = temp
                    temp = temp.left
                elif temp.val < currentnode.val:
                    temp = temp.right
            return lastnode
            
    def find_previous_node(self, currentnode, root):
        if currentnode is None or (currentnode.left is None and currentnode == root):
            return None
        if currentnode.left:
            temp = currentnode.left
            while temp.right:
                temp = temp.right
            return temp
        else:
            temp, lastnode = root, None
            while temp is not None and temp != currentnode:
                if temp.val > currentnode.val:
                    temp = temp.left
                elif temp.val < currentnode.val:
                    lastnode = temp
                    temp = temp.right
            return lastnode

problem convert sorted list to balanced binary search tree using divide and conquer:get mid node and connect with left and right
child
class Solution:
    def __init__(self):
        self.current = None
        
    def getlength(self, head):
        count = 0
        while head is not None:
            count += 1
            head = head.next
        return count
        
    def convert(self, length):
        if length == 0:
            return None
            
        elif length == 1:
            treenode = TreeNode(self.current.val)
            self.current = self.current.next
            return treenode
        
        else:  
            leftnode = self.convert(int(length/2))
            rootnode = TreeNode(self.current.val)
            rootnode.left = leftnode
            self.current = self.current.next
            if self.current is not None:
                rightnode = self.convert(length-int(length/2)-1)
                rootnode.right = rightnode
            return rootnode
        
    """
    @param: head: The first node of linked list.
    @return: a tree node
    """
    def sortedListToBST(self, head):
        # write your code here
        self.current = head
        return self.convert(self.getlength(head))
        
problem:using divide and conquer to solve the median of two sorted array
idea:our goal is to find the kth element in two sorted arrays, everytime we compare the k/2th element of both arrays, we remove
k/2 elements from the array with the smaller k/2th element since all k/2 elements in the smaller array will ahead the kth target
in two arrays !
def findkth(self, array1, array2, st_idx1, st_idx2, size1, size2, k):
        if st_idx1 == size1 and st_idx2 < size2: #if either array is empty, just return the kth element in the non-empty array
            return array2[st_idx2+k-1]
        elif st_idx2 == size2 and st_idx1 < size1:
            return array1[st_idx1+k-1]
        elif st_idx2 < size2 and st_idx1 < size1:
            if k == 1: #if k == 1, just the smallest member
                return min(array1[st_idx1],array2[st_idx2])
            else:
                if st_idx1+int(k/2)-1 < size1:
                    val_1 = array1[st_idx1+int(k/2)-1]
                else: #if no such index element exists, then return the maximum one to guarantee, the longer array will be tripped
                    val_1 = math.inf
                if st_idx2+int(k/2)-1 < size2:
                    val_2 = array2[st_idx2+int(k/2)-1]
                else:
                    val_2 = math.inf
                if val_1 < val_2:
                    return self.findkth(array1, array2, st_idx1+int(k/2), st_idx2, size1, size2, k-int(k/2))
                else:
                    return self.findkth(array1, array2, st_idx1, st_idx2+int(k/2), size1, size2, k-int(k/2))
main function:
sizea, sizeb = len(A), len(B)
        if (sizea+sizeb) % 2:
            return self.findkth(A, B, 0, 0, sizea, sizeb, math.ceil((sizea+sizeb)/2))
        else:
            return (self.findkth(A, B, 0, 0, sizea, sizeb, int((sizea+sizeb)/2)) + 
            self.findkth(A, B, 0, 0, sizea, sizeb, int((sizea+sizeb)/2)+1)) / 2