No. 199 - Binary Tree Right Side View

---

LeetCode 199 – Binary Tree Right Side View

題目描述

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example 1.

Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]

---

本題的目的是要找出 tree 的每一層最右邊的 node，但這並不代表就是從 root 開始的每一個 right child，因為並不一定向上面範例的 tree 從 root 開始都有 right child 存在。

這題我們將分別講解 Breadth First Search 跟 Depth First Search 的作法。

解法 1. Breadth First Search

BFS 的作法是先搜尋 tree 的每一層，而這題的目的是要找出每一層的最右邊的 node，所以只要每搜尋完一層，其最後的 node 就是我們要的。

完整的程式碼如下:

/**
 * 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<int> rightSideView(TreeNode* root) {
    vector<int> res;
    if (!root)
      return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
      int n = q.size();
      for (int i = 0; i < n; ++i) {
        root = q.front();
        q.pop();
        if (root->left)
          q.push(root->left);
        if (root->right)
          q.push(root->right);
      }
      res.push_back(root->val);
    }
    return res;
  }
};

BFS 的解法我們要先有一個用來存 nodes 的 queue。每一次的 while loop 就是搜尋 tree 的某一層，要知道一層有多少 node 只要看當前 queue 裡面的 node 數量即可 (第 21 行)，並在第 22 - 29 行把每次 pop 出來的 node 其 left/right child 依序地 push 到 queue 裡面，當一層的 node 都走訪過一遍了，最後一個 node 就是我們要的結果。

解法 2 Depth First Search

我們其實也可以不要都把每一層的所有 nodes 都走訪一便，而是盡可能的找下一層的最右邊的 node。這就是 DFS 的解法。完整的程式碼如下:

/**
 * 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:
  void dfs(TreeNode* node, int depth, vector<int> &res) {
    if (!node)
      return;
    if (res.size() < depth)
      res.push_back(node->val);
    depth++;
    dfs(node->right, depth, res);
    dfs(node->left, depth, res);
    return;
  }
  vector<int> rightSideView(TreeNode* root) {
    vector<int> res;
    dfs(root, 1, res);
    return res;
  }
};

我們設計一個 dfs 遞迴函式，這個函式有三個參數:

• node: 當前走訪的 node
• depth: 當前 node 所在層數 (以 root 所在初始層數為 1 開始計算)
• res: 紀錄最右邊 node 的 list

這個遞迴函式會優先走訪 right child 再走訪 left child (第 20 - 21 行)。

每次要走訪下一個 node 前都會先看會先看當前的 node 是不是這一層最右邊的 node，要如何知道是不是最右邊的 node? 因為我們是優先走訪 right child 所以我們第一次所到達的每一層一定會是最右邊的 node。那要怎麼知道當前走訪的 node 是否是該層第一次走訪到的呢? 只要我們看當前 res 裡的數量也就是已經紀錄的最右邊 nodes 的數量是否小於 depth 也就是當前 node 所在的層數即可知道是否為第一次到達該深度 (第 17 - 18 行)。

複雜度分析

時間複雜度

若是用 BFS 的解法，因為每一層的每個 node 都要走訪一遍，所以複雜度為

$O(N)$。

若是用 DFS 的解法，因為我們盡可能地只走訪每一層的最右邊的 node，所以複雜度為

$O(H)$。

空間複雜度

若是用 BFS 的解法，我們需要 queue 來存 node，而這個 queue 會需要的最大 size 就是 tree 中最多 nodes 的一層，其最差的情況為 perfect binary tree 的 leaf 那一層，複雜度為

$O(2^H)$。

若是用 DFS 的解法，我們需要儲存函式的 queue 來進行遞迴，因為其每次的遞迴都是走訪下一層 node，其複雜度為

$O(H)$。