Question

Formatted question description: https://leetcode.ca/all/314.html

 314	Binary Tree Vertical Order Traversal

 Given a binary tree, return the vertical order traversal of its nodes' values.
 (ie, 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.

 Examples:
 Given binary tree [3,9,20,null,null,15,7],

     3
    / \
   9  20
     /  \
    15   7
 return its vertical order traversal as:

 [
 [9],
 [3,15],
 [20],
 [7]
 ]


 Given binary tree [3,9,20,4,5,2,7],

     _3_
    /   \
   9    20
  / \   / \
 4   5 2   7
 return its vertical order traversal as:

 [
 [4],
 [9],
 [3,5,2],
 [20],
 [7]
 ]

 @tag-tree

Algorithm

How to determine the order of the columns, you can give the root node a sequence number of 0, and then start the traversal of the layer sequence. For any left child node, the sequence number is reduced by 1, and the right child node sequence number is increased by 1, so that the node value of the same column can be changed by the sequence number Put together

Another way, is to use a TreeMap to create a mapping between the sequence number and its corresponding node value.

advantage of using TreeMap is that its automatic sorting function allows the column to be sorted from left to right. Since the sequence traversal needs to use the queue, the queue cannot only be stored at this time for nodes, it is necessary to store a pair consisting of a sequence number and a node, so that the sequence number can be operated every time it is taken out, and the nodes in the queue are also assigned their correct sequence numbers.

Code

Java

// Time complexity O(n)
// Space complexity O(n)
public class Solution {
    private class TreeColumnNode{

        public TreeNode treeNode;
        int col;

        public TreeColumnNode(TreeNode node, int col) {
            this.treeNode = node;
            this.col = col;
        }
    }

    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null) {
            return res;
        }
        Queue<TreeColumnNode> queue = new LinkedList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        queue.offer(new TreeColumnNode(root, 0));
        int curLevelCount = 1;
        int nextLevelCount = 0;

        while(!queue.isEmpty()) {
            TreeColumnNode node = queue.poll();
            if(map.containsKey(node.col)) {
                map.get(node.col).add(node.treeNode.val);
            } else {
                map.put(node.col, new ArrayList<Integer>(Arrays.asList(node.treeNode.val)));
            }
            curLevelCount--;

            if(node.treeNode.left != null) {
                queue.offer(new TreeColumnNode(node.treeNode.left, node.col - 1));
                nextLevelCount++;
            }
            if(node.treeNode.right != null) {
                queue.offer(new TreeColumnNode(node.treeNode.right, node.col + 1));
                nextLevelCount++;
            }
            if(curLevelCount == 0) {
                curLevelCount = nextLevelCount;
                nextLevelCount = 0;
            }
        }

        return new ArrayList<List<Integer>>(map.values());
    }
}

// OJ: https://leetcode.com/problems/binary-tree-vertical-order-traversal/
// Time: O(NlogW) where N is the number of nodes in the tree and W is the width of the tree
// Space: O(N)
class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        if (!root) return {};
        map<int, vector<int>> m;
        queue<pair<TreeNode*, int>> q;
        q.emplace(root, 0);
        while (q.size()) {
            auto [node, index] = q.front();
            q.pop();
            m[index].push_back(node->val);
            if (node->left) q.emplace(node->left, index - 1);
            if (node->right) q.emplace(node->right, index + 1);
        }
        vector<vector<int>> ans;
        for (auto &[index, v] : m) ans.push_back(v);
        return ans;
    }
};

# 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 []
        q = deque([(root, 0)])
        d = defaultdict(list)
        while q:
            for _ in range(len(q)):
                root, offset = q.popleft()
                d[offset].append(root.val)
                if root.left:
                    q.append((root.left, offset - 1))
                if root.right:
                    q.append((root.right, offset + 1))
        return [v for _, v in sorted(d.items())]

############

# 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

'''
>>> d = {1:'a', -1:'b', 10:'c', -100:'d'}
>>>
>>> d.items()
{1: 'a', 10: 'c', -100: 'd', -1: 'b'}

>>> ds = sorted(d.items())
>>> ds
[(-100, 'd'), (-1, 'b'), (1, 'a'), (10, 'c')]

>>> sorted(d.items(), key=lambda l: l[1])
[(1, 'a'), (-1, 'b'), (10, 'c'), (-100, 'd')]
>>> dict(sorted(d.items(), key=lambda l: l[1]))
{1: 'a', 10: 'c', -100: 'd', -1: 'b'}

>>> [v for i,v in sorted(d.items(), key=lambda l: l[0])]
['d', 'b', 'a', 'c']
'''
class Solution:
    def verticalOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:
            return []
        q = deque([(root, 0)])
        d = defaultdict(list)
        while q:
            for _ in range(len(q)):
                root, offset = q.popleft()
                d[offset].append(root.val)
                if root.left:
                    q.append((root.left, offset - 1))
                if root.right:
                    q.append((root.right, offset + 1))
        return [v for _, v in sorted(d.items())]

#################

from collections import defaultdict

class Solution(object):
  def verticalOrder(self, root):
    """
    :type root: TreeNode
    :rtype: List[List[int]]
    """

    def dfs(p, i, j, res): # i -> depth, j -> vertical-shift
      if p:
        res[j].append((p.val, i))
        self.leftMost = min(j, self.leftMost)
        dfs(p.left, i + 1, j - 1, res)
        dfs(p.right, i + 1, j + 1, res)

    self.leftMost = float("inf")
    ans = []
    res = defaultdict(list)
    dfs(root, 0, 0, res)
    i = self.leftMost
    while True:
      if not res[i]:
        break
      ans.append([item[0] for item in sorted(res[i], key=lambda a: a[1])])
      i += 1
    return ans

TreeMap version

// Time complexity O(nlogn)
// Space complexity O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> verticalOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> q = new LinkedList<>();
        Queue<Integer> cols = new LinkedList<>();
        Map<Integer, List<Integer>> map = new TreeMap<>();
        q.offer(root);
        cols.offer(0);
        int min = 0, max = 0;
        while (!q.isEmpty()) {
            TreeNode cur = q.poll();
            int col = cols.poll();
            if (!map.containsKey(col)) map.put(col, new ArrayList<>());
            map.get(col).add(cur.val);
            if (cur.left != null) {
                q.offer(cur.left);
                cols.offer(col - 1);
                min = Math.min(min, col - 1);
            }
            if (cur.right != null) {
                q.offer(cur.right);
                cols.offer(col + 1);
                max = Math.max(max, col + 1);
            }
        }
        res.addAll(map.values());
        return res;
    }
}

// OJ: https://leetcode.com/problems/binary-tree-vertical-order-traversal/
// Time: O(NlogW) where N is the number of nodes in the tree and W is the width of the tree
// Space: O(N)
class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        if (!root) return {};
        map<int, vector<int>> m;
        queue<pair<TreeNode*, int>> q;
        q.emplace(root, 0);
        while (q.size()) {
            auto [node, index] = q.front();
            q.pop();
            m[index].push_back(node->val);
            if (node->left) q.emplace(node->left, index - 1);
            if (node->right) q.emplace(node->right, index + 1);
        }
        vector<vector<int>> ans;
        for (auto &[index, v] : m) ans.push_back(v);
        return ans;
    }
};

# 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 []
        q = deque([(root, 0)])
        d = defaultdict(list)
        while q:
            for _ in range(len(q)):
                root, offset = q.popleft()
                d[offset].append(root.val)
                if root.left:
                    q.append((root.left, offset - 1))
                if root.right:
                    q.append((root.right, offset + 1))
        return [v for _, v in sorted(d.items())]

############

from collections import defaultdict


class Solution(object):
  def verticalOrder(self, root):
    """
    :type root: TreeNode
    :rtype: List[List[int]]
    """

    def dfs(p, i, j, res):
      if p:
        res[j].append((p.val, i))
        self.leftMost = min(j, self.leftMost)
        dfs(p.left, i + 1, j - 1, res)
        dfs(p.right, i + 1, j + 1, res)

    self.leftMost = float("inf")
    ans = []
    res = defaultdict(list)
    dfs(root, 0, 0, res)
    i = self.leftMost
    while True:
      if not res[i]:
        break
      ans.append([item[0] for item in sorted(res[i], key=lambda a: a[1])])
      i += 1
    return ans

314 - Binary Tree Vertical Order Traversal

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions