Vertical order traversal of binary trees

Title Description

Given the root of a binary tree, calculate the vertical order traversal of the binary tree.

For each node at position (row, col), its left and right children will be at positions (row + 1, col – 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

Return the vertical order traversal of the binary tree.

Example 1:

Input: root = [3,9,20, null, null, 15, 7] Output: [[9], [3], [20], [7]] Explanation: the Column 1: Only node 9 is in this column. Column 0: Nodes 3 and 15 are in this column in that order from top to bottom. Column 1: Only node 20 is in this column. Column 2: Only node 7 is in this column.Copy the code

Example 2:

Input: root =,2,3,4,5,6,7 [1] the Output: [[4], [2], [1 and 6], [3], [7]] Explanation: the Column - 2: Only node 4 is 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 at the top, so it comes first. 5 and 6 are at the same position (2, 0), so we order them by their value, 5 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 =,2,3,4,6,5,7 [1] the Output: [[4], [2], [1 and 6], [3], [7]] Explanation: This case is the exact same as example 2, but with nodes 5 and 6 swapped. Note that the solution remains the same since 5 and 6 are in the same location and should be ordered by their values.Copy the code

Constraints:

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

Topic describes

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, 1000] 0 <= node. val <= 1000

Their thinking

1. Make a walk through the tree starting from the root node. Use the array Nodes to record the row number, col number and value of each node during the walk. 2. After the traversal is complete, sort all nodes. 3. Perform a traverse of nodes and place the values equal to row in the same array.

code

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number[][]}* /
var verticalTraversal = function (root) {

    constnodes = []; <! --1.Use the array Nodes to record the row number, col number and value of each node during the walk. --> dfs(root,0.0, nodes); <! --2.After the traversal is complete, all nodes are sorted. --> nodes.sort((a, b) = > {
        if (a[0] !== b[0]) {
            return a[0] - b[0];
        } else if (a[1] !== b[1]) {
            return a[1] - b[1];
        } else {
            return a[2] - b[2];
        }
    });


<!-- 3.Perform a traverse of Nodes, placing values equal to row in the same array. -->const ret = [];
    let min = -Number.MAX_VALUE;

    for (const x of nodes) {
        if(min ! == x[0]) {
            min = x[0];
            ret.push([]);
        }
        ret[ret.length - 1].push(x[2]);
    }

    returnret; }; <! -- create tree traversal function -->function dfs(node, row, col, nodes) {
    if (node === null) {
        return;
    }

    nodes.push([col, row, node.val]);

    dfs(node.left, row + 1, col - 1, nodes);
    dfs(node.right, row + 1, col + 1, nodes);
}



Copy the code