Question

314. Binary Tree Vertical Order Traversal

中文文档

Description

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

Solutions

Solution 1: DFS

DFS traverses the binary tree, recording the value, depth, and horizontal offset of each node. Then sort all nodes by horizontal offset from small to large, then by depth from small to large, and finally group by horizontal offset.

The time complexity is $O(n\log \log n)$, and the space complexity is $O(n)$. Where $n$ is the number of nodes in the binary tree.

# 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]]:
    def dfs(root, depth, offset):
      if root is None:
        return
      d[offset].append((depth, root.val))
      dfs(root.left, depth + 1, offset - 1)
      dfs(root.right, depth + 1, offset + 1)

    d = defaultdict(list)
    dfs(root, 0, 0)
    ans = []
    for _, v in sorted(d.items()):
      v.sort(key=lambda x: x[0])
      ans.append([x[1] for x in v])
    return ans

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val;
 *     this.left = left;
 *     this.right = right;
 *   }
 * }
 */
class Solution {
  private TreeMap<Integer, List<int[]>> d = new TreeMap<>();

  public List<List<Integer>> verticalOrder(TreeNode root) {
    dfs(root, 0, 0);
    List<List<Integer>> ans = new ArrayList<>();
    for (var v : d.values()) {
      Collections.sort(v, (a, b) -> a[0] - b[0]);
      List<Integer> t = new ArrayList<>();
      for (var e : v) {
        t.add(e[1]);
      }
      ans.add(t);
    }
    return ans;
  }

  private void dfs(TreeNode root, int depth, int offset) {
    if (root == null) {
      return;
    }
    d.computeIfAbsent(offset, k -> new ArrayList<>()).add(new int[] {depth, root.val});
    dfs(root.left, depth + 1, offset - 1);
    dfs(root.right, depth + 1, offset + 1);
  }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
using pii = pair<int, int>;

class Solution {
public:
  map<int, vector<pii>> d;

  vector<vector<int>> verticalOrder(TreeNode* root) {
    dfs(root, 0, 0);
    vector<vector<int>> ans;
    for (auto& [_, v] : d) {
      sort(v.begin(), v.end(), [&](pii& a, pii& b) {
        return a.first < b.first;
      });
      vector<int> t;
      for (auto& x : v) {
        t.push_back(x.second);
      }
      ans.push_back(t);
    }
    return ans;
  }

  void dfs(TreeNode* root, int depth, int offset) {
    if (!root) return;
    d[offset].push_back({depth, root->val});
    dfs(root->left, depth + 1, offset - 1);
    dfs(root->right, depth + 1, offset + 1);
  }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
func verticalOrder(root *TreeNode) [][]int {
  d := map[int][][]int{}
  var dfs func(*TreeNode, int, int)
  dfs = func(root *TreeNode, depth, offset int) {
    if root == nil {
      return
    }
    d[offset] = append(d[offset], []int{depth, root.Val})
    dfs(root.Left, depth+1, offset-1)
    dfs(root.Right, depth+1, offset+1)
  }
  dfs(root, 0, 0)
  idx := []int{}
  for i := range d {
    idx = append(idx, i)
  }
  sort.Ints(idx)
  ans := [][]int{}
  for _, i := range idx {
    v := d[i]
    sort.SliceStable(v, func(i, j int) bool { return v[i][0] < v[j][0] })
    t := []int{}
    for _, x := range v {
      t = append(t, x[1])
    }
    ans = append(ans, t)
  }
  return ans
}

Solution 2: BFS

A better approach to this problem should be BFS, traversing from top to bottom level by level.

The time complexity is $O(n\log n)$, and the space complexity is $O(n)$. Where $n$ is the number of nodes in the binary tree.

# 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.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode() {}
 *   TreeNode(int val) { this.val = val; }
 *   TreeNode(int val, TreeNode left, TreeNode right) {
 *     this.val = val;
 *     this.left = left;
 *     this.right = right;
 *   }
 * }
 */
class Solution {
  public List<List<Integer>> verticalOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) {
      return ans;
    }
    Deque<Pair<TreeNode, Integer>> q = new ArrayDeque<>();
    q.offer(new Pair<>(root, 0));
    TreeMap<Integer, List<Integer>> d = new TreeMap<>();
    while (!q.isEmpty()) {
      for (int n = q.size(); n > 0; --n) {
        var p = q.pollFirst();
        root = p.getKey();
        int offset = p.getValue();
        d.computeIfAbsent(offset, k -> new ArrayList()).add(root.val);
        if (root.left != null) {
          q.offer(new Pair<>(root.left, offset - 1));
        }
        if (root.right != null) {
          q.offer(new Pair<>(root.right, offset + 1));
        }
      }
    }
    return new ArrayList<>(d.values());
  }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *   int val;
 *   TreeNode *left;
 *   TreeNode *right;
 *   TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *   TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
  vector<vector<int>> verticalOrder(TreeNode* root) {
    vector<vector<int>> ans;
    if (!root) return ans;
    map<int, vector<int>> d;
    queue<pair<TreeNode*, int>> q{{{root, 0}}};
    while (!q.empty()) {
      for (int n = q.size(); n; --n) {
        auto p = q.front();
        q.pop();
        root = p.first;
        int offset = p.second;
        d[offset].push_back(root->val);
        if (root->left) q.push({root->left, offset - 1});
        if (root->right) q.push({root->right, offset + 1});
      }
    }
    for (auto& [_, v] : d) {
      ans.push_back(v);
    }
    return ans;
  }
};

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
func verticalOrder(root *TreeNode) [][]int {
  ans := [][]int{}
  if root == nil {
    return ans
  }
  d := map[int][]int{}
  q := []pair{pair{root, 0}}
  for len(q) > 0 {
    for n := len(q); n > 0; n-- {
      p := q[0]
      q = q[1:]
      root = p.node
      offset := p.offset
      d[offset] = append(d[offset], root.Val)
      if root.Left != nil {
        q = append(q, pair{root.Left, offset - 1})
      }
      if root.Right != nil {
        q = append(q, pair{root.Right, offset + 1})
      }
    }
  }
  idx := []int{}
  for i := range d {
    idx = append(idx, i)
  }
  sort.Ints(idx)
  for _, i := range idx {
    ans = append(ans, d[i])
  }
  return ans
}

type pair struct {
  node   *TreeNode
  offset int
}