LeetCode - 314 | hwchiu learning note

hwchiu learning note Blog

HungWei ChiuBlogger · 2017-03-01 · via hwchiu learning note Blog

314 Binary Tree Vertical Order Traversal

原題目是付費題目，有興趣看到完整的請自行付費觀賞，在此就不提供超連結了。

Introduction

給定一個 binary tree，將此 tree 以 vertical 的方式走過，
輸出時，從最左邊開始輸出
相同 colume 的算同一個 group，若屬於同 row 且同 colume，則從左邊開始算起

Example

輸出為 [2][1] [0,3,5][4,7] [6][8]

Solution

這題不太困難，基本上可以採用 BFS 來搜尋整個 tree，然後加入一個 index 的欄位，root 的 index 是 0，往左遞減，往右遞增，在 BFS 的過程中，就把相同 index 都收集起來，最後再一口氣輸出即可。

pseudo code 如下

queue.push(pair(0, root));
while (!queue.empty()) {
      index = queue.front().first;
      node = queue.front().second;

      ans[index].push(node->val)

      if (node->left)
          queue.push(pair(index-1, node->left);
      if (node->right)
          queue.push(pair(index+1, node->right);
}

return ans;

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

hwchiu learning note Blog

314 Binary Tree Vertical Order Traversal​

Introduction​

Example​

Solution​

314 Binary Tree Vertical Order Traversal

Introduction

Example

Solution