去洋山港行程码会不会变化_机械加工外协加工网_杭州网站seo外包_各个广告联盟的标识

题目描述

给定一棵二叉树的根节点，想象你站在它的右侧，返回你能看到的节点值（从上到下的顺序）。

示例：

输入：1/ \2   3\   \5   4
输出：[1,3,4]
解释：站在右侧时，只能看到每层最右边的节点

解题思路

这道题的核心是找到每一层最右边的节点。我们可以用递归的 DFS（深度优先搜索）来解决，但需要一点小技巧：

1. 右子树优先：遍历时先访问右子树，再访问左子树。这样当第一次到达某一深度时，遇到的节点一定是该层最右侧的节点。

2. 深度标记：维护一个全局变量 max_depth 记录当前已访问过的最大深度。只有当当前深度超过 max_depth 时，才记录节点值并更新最大深度。

举个栗子🌰：

• 对于示例中的树，遍历顺序是 1 → 3 → 4 → 2 → 5

• 当访问到节点 3（深度2）时，发现深度超过之前的 max_depth（初始为0），记录 3

• 接着访问 4（深度3），记录 4

• 最后访问 5（深度3），此时 max_depth 已经是3了，不再记录

---

代码实现

class Solution {
public:int max_depth = 0;  // 全局变量，记录当前最大深度void traversal(TreeNode *root, int depth, vector<int> &res) {if (!root) return;depth++;  // 进入节点时深度+1// 关键判断：首次到达新深度时记录节点值if (depth > max_depth) {max_depth = depth;     // 更新最大深度res.push_back(root->val); // 记录右侧节点}// 先递归右子树，再递归左子树（右子树优先）traversal(root->right, depth, res);traversal(root->left, depth, res);}vector<int> rightSideView(TreeNode* root) {if (!root) return {};  // 处理空树vector<int> res;traversal(root, 0, res);  // 初始深度为0return res;}
};

复杂度分析

• 时间复杂度：O(n)
  每个节点恰好被访问一次，没有重复操作。

• 空间复杂度：O(h)
  h 是树的高度，递归调用栈的深度最大为树高。最坏情况下（树退化为链表）空间复杂度为 O(n)。