題目

請根據二叉樹的前序遍歷，中序遍歷恢復二叉樹，并打印出二叉樹的右視圖

數據范圍：?0≤n≤100000≤n≤10000
要求： 空間復雜度?O(n)O(n)，時間復雜度?O(n)O(n)

如輸入[1,2,4,5,3],[4,2,5,1,3]時，通過前序遍歷的結果[1,2,4,5,3]和中序遍歷的結果[4,2,5,1,3]可重建出以下二叉樹：

C++代碼實現：

TreeNode* buildTree(vector<int> & xianxu, int l1, int r1, vector<int> &zhongxu, int l2, int r2){if (l1 > r1 || l2 > r2) return NULL;TreeNode* root = new TreeNode(xianxu[l1]);int rootIndex = 0;for (int i = l2; i <= r2; ++i){if (zhongxu[i] == xianxu[l1]){rootIndex = i;break;}}int leftsize = rootIndex - l2;int rightsize = r2 - rootIndex;root->left = buildTree(xianxu, l1+1, l1+leftsize, zhongxu, l2, l2+leftsize-1);root->right = buildTree(xianxu, l1+leftsize+1, r1, zhongxu, rootIndex+1, r2);return root;}vector<int> rightSideView(TreeNode *root){unordered_map<int, int> mp;int max_depth = -1;stack<TreeNode*> nodes;stack<int> depth;nodes.push(root);depth.push(0);while (!nodes.empty()){TreeNode* node = nodes.top();nodes.pop();int depth1 = depth.top();depth.pop();if (node != NULL)   {max_depth = max(depth1, max_depth);if (mp.find(depth1) == mp.end()){mp[depth1] = node->val;}nodes.push(node->left);nodes.push(node->right);depth.push(depth1+1);depth.push(depth1+1);} }vector<int> res;for (int i = 0; i <= max_depth; ++i){res.push_back(mp[i]);}return res;}vector<int> solve(vector<int>& preOrder, vector<int>& inOrder) {vector<int> res;if (preOrder.size() == 0) return res;TreeNode* root = buildTree(preOrder, 0, preOrder.size()-1, inOrder, 0, inOrder.size()-1);return rightSideView(root);}

右視圖是啥？

右視圖就是「站在二叉樹右邊看過去，能看到的每個層的最右邊節點」。比如下面這個樹：

    1        （第0層，看到1）/   \2     3     （第1層，看到3）
/     / \
4     5   6   （第2層，看到6）

右視圖結果就是?[1,3,6]—— 核心是要拿到「每一層的第一個遇到的最右節點」。

為什么用棧？棧在這里的作用

棧是 “先進后出” 的容器，適合深度優先遍歷（先往深了走，走到頭再回頭）。這里用了?兩個棧：

• nodes?棧：存要遍歷的二叉樹節點；
• depth?棧：存對應節點的 “深度”（根節點深度是 0，子節點比父節點深 1）。
  兩個棧是 “同步操作” 的 —— 彈出一個節點，就對應彈出它的深度；壓入節點時，也對應壓入它的深度。

逐行拆解代碼邏輯（結合例子看更清楚）

咱們就用上面的樹?[1,2,3,4,5,6]?當例子，一步一步看棧和數據的變化。

初始狀態

一開始，把根節點?1?和它的深度?0?分別壓入兩個棧：

• nodes?棧：[1]（棧頂是 1）
• depth?棧：[0]（棧頂是 0）
• mp（存 “深度→最右節點值”）：空
• max_depth（記錄最大深度）：-1

進入循環：while (!nodes.empty ())（棧不空就繼續）

循環的核心邏輯是：彈出棧頂節點→判斷是不是有效節點→處理有效節點→壓入它的子節點。

第一步：彈出節點和對應深度

TreeNode* node = nodes.top();  // 取nodes棧頂節點（一開始是1）
nodes.pop();                   // 把1從nodes棧彈出，nodes現在空了
int depth1 = depth.top();      // 取depth棧頂深度（0）
depth.pop();                   // 把0從depth棧彈出，depth現在空了

此時：node=1，depth1=0。

第二步：判斷節點是否有效（非 NULL）

if (node != NULL)  // 1不是NULL，進入處理
{// 1. 更新最大深度：當前深度0比初始的-1大，所以max_depth=0max_depth = max(depth1, max_depth);  // max(0,-1)=0// 2. 記錄當前深度的最右節點（關鍵！）if (mp.find(depth1) == mp.end())  // 查mp里有沒有深度0的記錄？一開始沒有{mp[depth1] = node->val;  // 把深度0和值1存進去，mp現在是 {0:1}}// 3. 壓入當前節點的左、右子節點（重點！棧是先進后出，所以先壓左，再壓右）nodes.push(node->left);   // 壓入1的左子節點2 → nodes棧：[2]nodes.push(node->right);  // 再壓入1的右子節點3 → nodes棧：[2,3]（棧頂是3）// 4. 同步壓入子節點的深度（父節點深度+1=0+1=1）depth.push(depth1+1);  // 壓入2的深度1 → depth棧：[1]depth.push(depth1+1);  // 再壓入3的深度1 → depth棧：[1,1]（棧頂是1）
}

這一步結束后

• nodes?棧：[2,3]（棧頂是 3）
• depth?棧：[1,1]（棧頂是 1）
• mp：{0:1}
• max_depth：0

第三步：繼續循環（nodes 棧不空，處理棧頂的 3）

重復第一步：彈出節點和深度

• node = nodes.top()?→ 3；nodes.pop()?→ nodes 變成 [2]
• depth1 = depth.top()?→ 1；depth.pop()?→ depth 變成 [1]

判斷 3 非 NULL，進入處理：

1. 更新 max_depth：max (1,0)=1 → max_depth=1；
2. 查 mp 有沒有深度 1 的記錄？沒有 → mp [1]=3 → mp 現在 {0:1, 1:3}；
3. 壓入 3 的左、右子節點：
   • 3 的左是 5，右是 6 → 先壓左（5），再壓右（6）→ nodes 棧變成 [2,5,6]（棧頂是 6）；
4. 同步壓入深度 1+1=2 → depth 棧變成 [1,2,2]（棧頂是 2）。

這一步結束后：

• nodes?棧：[2,5,6]
• depth?棧：[1,2,2]
• mp：{0:1, 1:3}
• max_depth：1

第四步：繼續循環（處理棧頂的 6）

彈出 6 和深度 2：

• node=6，depth1=2（非 NULL）；

1. 更新 max_depth：max (2,1)=2 → max_depth=2；
2. 查 mp 有沒有深度 2 的記錄？沒有 → mp [2]=6 → mp 現在 {0:1,1:3,2:6}；
3. 壓入 6 的左、右子節點（都是 NULL）→ nodes 棧變成 [2,5,NULL,NULL]；
4. 同步壓入深度 3 → depth 棧變成 [1,2,3,3]。

這一步后，mp?已經存好了所有層的最右節點，后續再處理 NULL 節點和剩下的 2、5，都不會修改 mp 了（因為 mp 里對應深度已有值）。

后續循環：處理 NULL 和剩余節點

比如處理 6 的左子節點（NULL）：彈出后判斷是 NULL，直接跳過，不做任何處理；
處理 5 時，深度是 2，但 mp 里已有深度 2 的記錄（6），所以不會覆蓋；
處理 2 時，深度是 1，mp 里已有深度 1 的記錄（3），也不會覆蓋。

直到棧空，循環結束。

最后：生成結果

vector<int> res;
for (int i = 0; i <= max_depth; ++i)  // 從深度0到2，依次取mp的值
{res.push_back(mp[i]);  // 0→1，1→3，2→6 → res=[1,3,6]
}
return res;

關鍵：為什么先壓左子節點，再壓右子節點？

這是保證拿到「最右節點」的核心
因為棧是 “先進后出”：先壓左，再壓右 → 下一次彈出時，會先彈右子節點。
比如節點 1 的子節點：先壓 2，再壓 3 → 下次先彈 3（右節點），這樣 3 就會被優先處理，成為深度 1 的最右節點；
節點 3 的子節點：先壓 5，再壓 6 → 下次先彈 6（右節點），成為深度 2 的最右節點。

如果反過來先壓右再壓左，就會先處理左節點，拿到的就是「左視圖」了

總結：這段代碼的邏輯一句話說

用兩個棧同步存節點和深度，通過 “先壓左、再壓右” 保證每次先處理層的右節點，用哈希表記錄每一層第一個遇到的右節點（就是最右節點），最后按深度順序收集結果，就是右視圖。