199. 二叉树的右视图

199. 二叉树的右视图 - 力扣（LeetCode）

class Solution {
public:
  vector<int> rightSideView(TreeNode* root) {
    if (!root)
      return {};

    vector<int> V;
    queue<TreeNode *> Q;
    Q.push(root);

    while (!Q.empty()) {
      TreeNode *Right = Q.back();
      V.push_back(Right->val);

      int Size = Q.size();
      for (int i = 0; i < Size; ++i) {
        TreeNode *TN = Q.front();
        Q.pop();

        if (TN->left)
          Q.push(TN->left);
        if (TN->right)
          Q.push(TN->right);
      }
    }

    return V;
  }
};

层序遍历模板题。二刷的时候用深搜写一下。

二刷 

class Solution {
public:
  vector<int> rightSideView(TreeNode* root) {
    std::queue<TreeNode *> Q;
    std::vector<int> Result;
    if (!root)
      return {};

    Q.push(root);
    while (!Q.empty()) {
      int LayerSize = Q.size();
      for (int i = 0; i < LayerSize; ++i) {
        TreeNode *This = Q.front();
        Q.pop();
        if (This->left)
          Q.push(This->left);
        if (This->right)
          Q.push(This->right);
        if (i == LayerSize - 1)
          Result.push_back(This->val);
      }
    }
    return Result;
  }
};

没什么好说的，层序遍历而已。但是你仔细看的话会发现我一刷的时候那个解法是更好的，避免了这个蹩脚的 i == LayerSize - 1 的判定。

至于递归深搜，也很好写，先访问右子树即可。

class Solution {
  vector<int> Result;
  void Traverse(TreeNode *TN, int Depth) {
    if (!TN)
      return;

    if (Depth == Result.size())
      Result.push_back(TN->val);
    Traverse(TN->right, Depth + 1);
    Traverse(TN->left, Depth + 1);
  }
public:
  vector<int> rightSideView(TreeNode* root) {
    Traverse(root, 0);
    return Result;
  }
};

迭代深搜注意栈是后进先出的，所以 emplace() 的顺序确实是先 left 再 right。

class Solution {
public:
  vector<int> rightSideView(TreeNode* root) {
    vector<int> Result;
    // type Pair = (TN, Depth);
    stack<pair<TreeNode *, int>> S;
    S.emplace(root, 0);
    while (!S.empty()) {
      auto [TN, Depth] = S.top();
      S.pop();
      if (!TN)
        continue;

      if (Depth == Result.size())
        Result.push_back(TN->val);
      // Stack is FILO, so [left, right] -> [right, left]. This is correct. If
      // we want a normal traversal, that's the time we push right first.
      S.emplace(TN->left, Depth + 1);
      S.emplace(TN->right, Depth + 1);
    }
    return Result;
  }
};

先右后左的前序遍历，外加对 Result.size() 的判断，保证了当且仅当我们访问到每一层的最右节点，Result 得以更新。

三刷 

class Solution {
public:
  vector<int> rightSideView(TreeNode* root) {
    if (!root)
      return {};

    vector<int> Result;
    queue<TreeNode *> Q;
    Q.push(root);
    while (!Q.empty()) {
      int Size = Q.size();
      for (int i = 0; i < Size; ++i) {
        TreeNode *TN = Q.front();
        Q.pop();
        if (i == Size - 1)
          Result.emplace_back(TN->val);
        if (TN->left)
          Q.push(TN->left);
        if (TN->right)
          Q.push(TN->right);
      }
    }
    return Result;
  }
};

还是采用了二刷而非一刷的写法。不过一刷那个Q.back()确实聪明啊。