LeetCode 314. Binary tree vertical order traversal - Binary Tree Series Question 6

Given the root of a binary tree, return the vertical order traversal of its nodes' values. (i.e., from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]

Example 2:

Input: root = [3,9,8,4,0,1,7]
Output: [[4],[9],[3,0,1],[8],[7]]

Example 3:

Input: root = [3,9,8,4,0,1,7,null,null,null,2,5]
Output: [[4],[9,5],[3,0,1],[8,2],[7]]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

The topic requires traversing the binary tree in vertical order , It's from the top to the bottom , Nodes in the same column are put into an array , The final result is a two-dimensional array composed of all column arrays . About the definition of columns ： Suppose the column number of a node is col, Then its left child node is col-1, The column number of the right child node is col+1.

Because we are familiar with the horizontal sequence traversal algorithm , Therefore, this problem is based on horizontal sequence traversal , Assign a column number to each node , In this way, node values with the same column number can be put together . First, specify the column number of the root node as 0, Then traverse in horizontal order , In this way, the column number of the node on the left of the root node is negative , Starting from the root node, the column number decreases every time you move to the left 1; The column number of the node on the right of the root node is positive , Starting from the root node, the column number will be added at every position to the right 1; The column number of the node in the same column as the root node is 0. For ease of handling , You can use a two-dimensional array to store the root node and all the columns on its left , The index of an array is the opposite of the column number （ That is, the column number is 0, -1,  -2, ... The corresponding array index is 0, 1, 2, ...）, Then use a two-dimensional array to store all the columns on the right of the root node （ Because the column number is 0 To the left array , Therefore, the column number is 1, 2, 3, ... The corresponding array index is 0, 1, 2, ...）. So when doing horizontal traversal , You can put the node in the corresponding position of the left or right array in real time according to the column number . For the left array , Whenever the absolute value of the column number is equal to the total number of arrays, a new column is added ; For the right array , Whenever the column number is greater than the total number of arrays, a new column is added .

    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        llist, rlist = [], []
        
        lindex, rindex = 0, 1
        
        q = deque([(root, 0)])
        while q:
            n = len(q)
            for i in range(n):
                node, index = q.popleft()
                if index <= 0:
                    if len(llist) > -index:
                        llist[-index].append(node.val)
                    else:
                        llist.append([node.val])
                else:
                    if len(rlist) > index - 1:
                        rlist[index - 1].append(node.val)
                    else:
                        rlist.append([node.val])
                if node.left:
                    q.append((node.left, index - 1))
                if node.right:
                    q.append((node.right, index + 1))
        llist.reverse()
        return llist + rlist