leetcode：199. 二叉树的右视图

题目

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1：
[中等] 199. 二叉树的右视图 - 图1

  1. 输入: [1,2,3,null,5,null,4]
  2. 输出: [1,3,4]

示例 2：

  1. 输入: [1,null,3]
  2. 输出: [1,3]

示例 3：

  1. 输入: []
  2. 输出: []

解答 & 代码

解法一：DFS 递归遍历

先遍历右子树，在遍历左子树
递归同时记录深度，若深度 > 结果数组长度，说明当前节点是这一层最先遍历到的，即这一层的最右节点，存入结果数组

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. private:
  14.     vector<int> result;
  15.     void dfs(TreeNode* root, int depth)
  16.     {
  17.         if(root == nullptr)
  18.             return;
  20.         if(result.size() < depth)
  21.             result.push_back(root->val);
  22.         dfs(root->right, depth + 1);
  23.         dfs(root->left, depth + 1);
  24.     }
  25. public:
  26.     vector<int> rightSideView(TreeNode* root) {
  27.         dfs(root, 1);
  28.         return result;
  29.     }
  30. };

复杂度分析：设二叉树节点数为 N

  • 时间复杂度 O(N)：
  • 空间复杂度 O(logN)：递归栈深度 = 二叉树高度

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：11.6 MB, 在所有 C++ 提交中击败了 81.84% 的用户

解法二：层序遍历

层序遍历，存储每层的最后一个节点

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     vector<int> rightSideView(TreeNode* root) {
  15.         if(root == nullptr)
  16.             return {};
  18.         vector<int> result;
  19.         queue<TreeNode*> nodeQ;
  20.         nodeQ.push(root);
  21.         while(!nodeQ.empty())
  22.         {
  23.             int levelSize = nodeQ.size();
  24.             for(int i = 0; i < levelSize; ++i)
  25.             {
  26.                 TreeNode* cur = nodeQ.front();
  27.                 nodeQ.pop();
  28.                 if(i == levelSize - 1)
  29.                     result.push_back(cur->val);
  30.                 if(cur->left != nullptr)
  31.                     nodeQ.push(cur->left);
  32.                 if(cur->right != nullptr)
  33.                     nodeQ.push(cur->right);
  34.             }
  35.         }
  36.         return result;
  37.     }
  38. };

复杂度分析：设二叉树节点数为 N

  • 时间复杂度 O(N)：
  • 空间复杂度 O(N)：队列的空间复杂度 O(N)

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：11.5 MB, 在所有 C++ 提交中击败了 94.27% 的用户