Problem 06 — Print the linked list from end to end

Enter the head node of a linked list and return the value of each node from end to end (as an array). The difficulty is easy

Ideas and code

It’s a little bit easier for Python to just walk through the linked list and get the value of the node into the list and flip the list

class Solution:
    def reversePrint(self, head: ListNode) - >List[int] :
        if not head:
            return []

        res = []

        while head:
            res.append(head.val)
            head = head.next

        return res[::-1]
Copy the code

Topic 07 — Rebuilding a binary tree

Enter the results of preorder and middle order traversal of a binary tree, please rebuild the binary tree. It is assumed that the result of both the preceding and the middle traversal of the input does not contain duplicate numbers. The difficulty is medium

Train of thought

For a binary tree, the pre-traversal order is left to right, and the middle-traversal order is left to right.

     3
    / \
   9   20
  / \  / \
 8  4 15  7
Copy the code

Take the above binary tree as an example, its foreorder traversal is [3,9,8,4,20,15,7], and its middle order traversal is [8,9,4,3,15,20,7]. I have been thinking for a long time and have no particularly good idea, so I will write it directly according to the official solution of the problem.

We start with a stack that maintains all the ancestors of the current node that have not considered the right son, with the current element at the top of the stack. Because middle-order traversal is left-middle-right, the first element of middle-order traversal must be the right-most looking element in the binary tree. We use index to point to the first element of the middle traversal, and its corresponding node is the final node from the current node to the left. In the above example, the first element 8 in the middle order traversal corresponds to the end of the previous order traversal of the first element 3 to the left.

First we push the root node 3 to the stack, then initialize the node to which index points to 8. Then for each node in the preceding traversal, we determine whether it is the left son of the top node or the right son of a node in the stack.

If 9 is traversed first, it is found to be the left son of 3. The reason is that if 9 is the right son, then the tree has no left son. The first element of the middle traversal should be the first element of the previous traversal. The same thing goes for 8. The stack elements are [3,9,8]

When iterating through element 4, we find that the top element of the stack is 8, and the index of the middle traversal points to the element 8, indicating that 4 does not have a left son, but is the right son of a node in the stack.

So how do we find this node? The order of the nodes in the stack is the same as the order in which they appear in the preceding traversal, and since the right son of each node has not been traversed yet, the order of the nodes must be the opposite of the order in which they appear in the middle traversal.

So move index to the right and compare it to the top of the stack. If it is the same, pop off the top of the stack and increase index by 1 until the first unequal comparison occurs, and the last popup is the parent of the right-changed son.

In this case, 8 and 8 compare, equal, index+ 1,8 out of the stack; Compare 9 to 9, equal, index+ 1,9 out of the stack. If 3 and 4 are not equal, then 4 is the right son of the last pop-up element, 9. We’re going to push 4. At this point, the stack is [3,4], and index points to element 4 in the middle traversal. Repeat the above steps, pop 4 and 3, and index moves to the right, leaving the stack empty and index pointing to element 15 in the middle traversal.

Then the problem is simplified to the reconstruction of binary trees with foreorder traversal of [20,15,7] and middle order traversal of [15,20,7].

   20
   / \
  15  7
Copy the code

And then you reconstruct the entire binary tree.

code

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
            return None
            
        root = TreeNode(preorder[0])
        stack = [root]
        index = 0

        for i in range(1.len(preorder)):
            preval = preorder[i]
            stacktop = stack[-1]
            
            ifstacktop.val ! = inorder[index]: stacktop.left = TreeNode(preval) stack.append(stacktop.left)else:
                while stack and stack[-1].val == inorder[index]:
                    stacktop = stack.pop()
                    index+=1
                stacktop.right = TreeNode(preval)
                stack.append(stacktop.right)
                
        return root
Copy the code