314. Binary Tree Vertical Order Traversal & 987

Problem Statement

link: LeetCode.cn LeetCode 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:

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

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

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

Solution Approach

The first solution uses a depth-first search (DFS) approach to traverse the binary tree and store node values in a dictionary based on their vertical and row positions, while the second solution employs a breadth-first search (BFS) with a queue to achieve the same vertical order traversal.

Algorithm

Solution 1: Depth-First Search (DFS) 1.Traverse the Tree: Perform a DFS starting from the root, and at each node, store its value in a dictionary using its column as the key and (row, value) as the tuple. 2.Track Column Range: Update the minimum and maximum column values during traversal to determine the range of columns for output. 3.Sort and Collect Results: After traversal, sort the nodes within each column by their row value, and then collect the values in order to form the vertical order traversal.

Solution 2: Breadth-First Search (BFS) 1.Initialize Queue: Use a queue to perform a BFS, starting from the root, and store each node along with its column and row positions in a dictionary. 2.Traverse Level by Level: Dequeue nodes level by level, updating the dictionary with their (row, value) pairs, and enqueue their left and right children with updated column and row positions. 3.Sort and Collect Results: Once traversal is complete, sort the dictionary by columns, and for each column, sort by row values before collecting the node values to form the final vertical order traversal.

Implement

    Definition for a binary tree node.
 class TreeNode:
     def __init__(self, val=0, left=None, right=None):
         self.val = val
         self.left = left
         self.right = right
 class Solution:
     def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
         if root is None:
             return []
         dic = defaultdict(list)
         min_column = max_column = 0
         def dfs(node, row, column):
             if node is not None:
                 nonlocal min_column, max_column
                 dic[column].append((row, node.val))
                 min_column = min(min_column, column)
                 max_column = max(max_column, column)
                 dfs(node.left, row + 1, column - 1)
                 dfs(node.right, row + 1, column + 1)
         dfs(root, 0, 0)
         ret = []
         for col in range(min_column, max_column + 1):
             dic[col].sort(key=lambda x:x[0])
             colVals = [val for row, val in dic[col]]
             ret.append(colVals)

         return ret
 
 class Solution:
     def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
         if not root:
             return []
         dic = defaultdict(list)
         q = deque([(root, 0, 0)])
         while q:
             node, level, row = q.popleft()
             dic[level].append((row, node.val))
             if node.left:
                 q.append((node.left, level - 1, row + 1))
             if node.right:
                 q.append((node.right, level + 1, row + 1))
         res = []
         for level, r_v in sorted(dic.items()):
             values = [v for r, v in r_v]
             res.append(values)
         
         return res
     

    
    

Twitter  facebook  Email