This article is participating in Python Theme Month. See the link to the event for more details

Topic describes

This is the vertical order traversal of the 987. Binary tree on LeetCode, difficulty is difficult.

Tag: Data structure utilization, binary tree, hash table, Sort, Priority queue, DFS

Given the root of the binary tree, you design an algorithm to calculate the vertical order traversal sequence of the binary tree.

For each node located in (row, col), the left and right children are located in (row + 1, col -1) and (row + 1, col + 1). The root of the tree is at (0, 0).

The vertical order traversal of the binary tree starts from the leftmost column to the rightmost column, and indexes all nodes in each column by column, forming an ordered list in order of occurrence from top to bottom. If there are more than one node in the same row in the same column, the node value is sorted from smallest to largest.

Returns the vertically ordered traversal sequence of a binary tree.

Example 1:

Input: root = [3,9,20,null,null,15,7] output: [[9],[3,15],[20],[7] explanation: column -1: only node 9 is in this column. Column 0: Only nodes 3 and 15 are in this column, in top to bottom order. Column 1: Only node 20 is in this column. Column 2: Only node 7 is in this column.Copy the code

Example 2:

Output: input: root =,2,3,4,5,6,7 [1], [[4], [2], [1 and 6], [3], [7]] : - 2:4 only nodes in this column. Column -1: Only node 2 is in this column. Column 0: nodes 1, 5, and 6 are in this column. 1 is up here, so it appears in front. Both the 5 and 6 positions are (2, 0), so order from smallest to largest, with 5 coming before 6. Column 1: Only node 3 is in this column. Column 2: Only node 7 is in this column.Copy the code

Example 3:

Input: root = [1,2,3,4,6,5,7] output: [[4],[2],[1,5,6],[3],[7] Because the 5 and 6 are still in the same position, the answer remains the same, and the values are still sorted from smallest to largest.Copy the code

Tip:

  • The total number of nodes in the tree is in the range [1, 10]

DFS + hash table + sort

According to the question, we need to construct the answer according to the priority “column number from small to large”, for nodes in the same column, “row number from small to large”, for elements in the same column, “node value from small to large”.

So we can walk through the tree, write down the information as we walk (col,row,val)(COL,row,val)(COL,row,val), sort it according to the rules, and construct the answer.

We can use a “hash table” for storage and then sort it once.

Java code:

class Solution {
    Map<TreeNode, int[]> map = new HashMap<>(); // col, row, val
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        map.put(root, new int[] {0.0, root.val});
        dfs(root);
        List<int[]> list = new ArrayList<>(map.values());
        Collections.sort(list, (a, b)->{
            if (a[0] != b[0]) return a[0] - b[0];
            if (a[1] != b[1]) return a[1] - b[1];
            return a[2] - b[2];
        });
        int n = list.size();
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; ) {
            int j = i;
            List<Integer> tmp = new ArrayList<>();
            while (j < n && list.get(j)[0] == list.get(i)[0]) tmp.add(list.get(j++)[2]);
            ans.add(tmp);
            i = j;
        }
        return ans;
    }
    void dfs(TreeNode root) {
        if (root == null) return ;
        int[] info = map.get(root);
        int col = info[0], row = info[1], val = info[2];
        if(root.left ! =null) {
            map.put(root.left, new int[]{col - 1, row + 1, root.left.val});
            dfs(root.left);
        }
        if(root.right ! =null) {
            map.put(root.right, new int[]{col + 1, row + 1, root.right.val}); dfs(root.right); }}}Copy the code

Python 3 code:

class Solution:
    def verticalTraversal(self, root: TreeNode) - >List[List[int]] :
        def dfs(node) :
            if not node:
                return
            col, row, val = hashmap[node]
            if node.left:
                hashmap[node.left] = [col - 1, row + 1, node.left.val]
                dfs(node.left)
            if node.right:
                hashmap[node.right] = [col + 1, row + 1, node.right.val]
                dfs(node.right)

        hashmap = dict(a)# col, row, val
        hashmap[root] = [0.0, root.val]
        dfs(root)
        lt = sorted(hashmap.values()) # equivalent to add key=lambda x:(x[0], x[1], x[2])
        n = len(lt)
        ans = []
        i = 0
        while i < n:
            j = i
            tmp = []
            while j < n and lt[j][0] == lt[i][0]:
                tmp.append(lt[j][2])
                j += 1
            ans.append(tmp)
            i = j
        return ans
Copy the code
  • Time complexity: let the total number of nodes be NNN, the tree traversal is carried out when the hash table is filled, and the complexity is O(n)O(n)O(n); The answer is constructed in order (nlog⁡n)O(n\log{n})O(nlogn). O(nlog⁡n)O(n\log{n})O(nlogn)
  • Space complexity: O(n)O(n)O(n)

DFS + Priority Queue (heap)

Obviously, in the end, to keep the corresponding information of all nodes in order, you can use a “priority queue (heap)” to maintain order along with storage.

Java code:

class Solution {
    PriorityQueue<int[]> q = new PriorityQueue<>((a, b)->{ // col, row, val
        if (a[0] != b[0]) return a[0] - b[0];
        if (a[1] != b[1]) return a[1] - b[1];
        return a[2] - b[2];
    });
    public List<List<Integer>> verticalTraversal(TreeNode root) {
        int[] info = new int[] {0.0, root.val};
        q.add(info);
        dfs(root, info);
        List<List<Integer>> ans = new ArrayList<>();
        while(! q.isEmpty()) { List<Integer> tmp =new ArrayList<>();
            int[] poll = q.peek();
            while(! q.isEmpty() && q.peek()[0] == poll[0]) tmp.add(q.poll()[2]);
            ans.add(tmp);
        }
        return ans;
    }
    void dfs(TreeNode root, int[] fa) {
        if(root.left ! =null) {
            int[] linfo = new int[]{fa[0] - 1, fa[1] + 1, root.left.val};
            q.add(linfo);
            dfs(root.left, linfo);
        }
        if(root.right ! =null) {
            int[] rinfo = new int[]{fa[0] + 1, fa[1] + 1, root.right.val}; q.add(rinfo); dfs(root.right, rinfo); }}}Copy the code

Python 3 code:

class Solution:
    def verticalTraversal(self, root: TreeNode) - >List[List[int]] :
        def dfs(node, fa) :
            if node.left:
                linfo = (fa[0] -1,fa[1] +1,node.left.val)
                heapq.heappush(q, linfo)
                dfs(node.left, linfo)
            if node.right:
                rinfo = (fa[0] +1,fa[1] +1,node.right.val)
                heapq.heappush(q, rinfo)
                dfs(node.right, rinfo)

        info = (0.0, root.val)
        q = [info]
        dfs(root, info)
        ans = []
        while q:
            tmp = []
            poll = q[0] [0]
            while q and q[0] [0] == poll:
                tmp.append(heapq.heappop(q)[2])
            ans.append(tmp)
        return ans
Copy the code
  • Time complexity: let the total number of nodes be NNN, and the complexity of storing node information into the priority queue (heap) is O(nlog⁡n)O(n\log{n})O(nlogn); The complexity of constructing the answer is O(nlog⁡n)O(n\log{n})O(nlogn). O(nlog⁡n)O(n\log{n})O(nlogn)
  • Space complexity: O(n)O(n)O(n)

The last

This is article No.987 in our “Brush through LeetCode” series, which began on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some with locks, and we will first brush through all the questions without locks.

In this series of articles, in addition to explaining how to solve the problem, I’ll give you the most concise code possible. If the general solution is involved, the corresponding code template will be provided.

In order to facilitate the students to debug and submit the code on the computer, I set up a related warehouse: github.com/SharingSour… .

In the repository address, you can see the solution to the series, the corresponding code to the series, the LeetCode link, and other preferred solutions to the series.