【C++】二叉樹進階面試題

根據二叉樹創建字符串

在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述

重點是要注意括號省略問題,分為以下情況:
1.左字樹為空,右子樹不為空,左邊括號保留
2.左右子樹都為空,括號都不保留
3。左子樹不為空,右子樹為空,右邊括號不保留
在這里插入圖片描述
如果根節點為空,返回空字符串。創建一個字符串將根節點的值轉換為字符串并存儲在 str 中,將整數值轉化為字符串目的可以直接進行追加操作。
代碼邏輯:
1.本質上是一個前序遍歷,在遍歷前加‘(‘遍歷后加’)’
2.左子樹加括號的條件用if(root->left||root->right)就完美描述,左子樹為空判斷第二個條件,右子樹也不為空就+(),若第一條件左子樹不為空直接成立也+()。調用左子樹遞歸來追加key值到字符串中
2.只要右子樹不為空就加(),調用右子樹遞歸來追加key值到字符串中

二叉樹的最近公共祖先

在這里插入圖片描述
在這里插入圖片描述

若直接是一棵搜索二叉樹,能確定pq大小,在左子樹還是右子樹。
一般情況下普通樹情況居多,思路:
1.一個在左邊,一個在右邊,當前根就是公共祖先
2.p或q就是根,另外一個在其子樹中,當前根就是公共祖先

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/bool find(TreeNode* root,TreeNode* x){if(root==nullptr){return false;}return root==x||find(root->left,x)||find(root->right,x);}
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==nullptr)return nullptr;//處理根節點就是pq情況if(root==p||root==q){return root;}bool pinleft,pinright,qinleft,qinright;pinleft=find(root->left,p);pinright=!pinleft;qinleft=find(root->left,q);qinright=!qinleft;//處理pq都在左邊情況if(pinleft&&qinleft){return lowestCommonAncestor(root->left, p, q);}//處理都在右邊情況else if(pinright&&qinright){return lowestCommonAncestor(root->right, p, q);}//處理一左一右情況else{return root;}}
};

代碼邏輯:
1.創建一個find函數去查找pq值所在節點,當前根不是就按前序遞歸查找
2.創建pinleft等狀態值,通過調用find函數來確定pq的存在情況
3.處理pq都在左子樹和右子樹情況,分別調用遞歸,成功返回root節點
4.最后pq一左一右情況直接返回根節點
精髓在于,通過遞歸從整個二叉樹逐步縮小樹的范圍,pq最終會呈現出一左一右的情況。

時間復雜度分析:
find 函數最壞情況下,可能需要訪問子樹中的所有節點,需要遍歷 O(n) 個節點。lowestCommonAncestor 函數 最壞情況下,如樹是完全不平衡的(退化為鏈式結構),此時遞歸調用的次數為 O(n),所以總的時間復雜度為 O(n2)。

倒著走,轉化為鏈表相交類似問題

 bool FindPath(TreeNode* root, TreeNode* x, stack<TreeNode*>&path){if(root==nullptr)return false;//先入棧再去判斷path.push(root);if(root==x)return true;//左右遞歸分別尋找if(FindPath(root->left,x,path))return true;if(FindPath(root->right,x,path))return true;//找不到pop掉該路節點,換路尋找path.pop();return false;}
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*>ppath,qpath;FindPath(root,p,ppath);FindPath(root,q,qpath);//長的先走差距步,兩種情況while(ppath.size()>qpath.size()){ppath.pop();}while(qpath.size()>ppath.size()){qpath.pop();}//一起走,尋找相交節點while(ppath.top()!=qpath.top()){ppath.pop();qpath.pop();}return ppath.top();}
};

FindPath查找路徑函數,利用棧后進先出的特性來實現。
1.空節點返回失敗,不為空先入棧,在判斷是否為目標值
2.當前節點為目標值返回成功,否則通過if條件套用去遞歸按照前序遍歷尋找
3.若沒找到,要pop節點,告訴父節點該方向沒有,換一個方向
lowestCommonAncestor 函數
1.pq分別創建一個棧,通過路徑查找函數招到各自路徑
2.相交鏈表處理思路,長的先走差距步,再一起走,第一次相遇點即為相交點。
3.長的先走,只要長度長于短的通過循環pop掉,最后一起走只要不相等就pop掉,最后隨便返回一個棧頂元素,有可能為空。

二叉樹搜索樹轉換成排序雙向鏈表

在這里插入圖片描述

在這里插入圖片描述

思路:
因要轉化成一個排序的雙向鏈表,所以要用到中序遍歷,至于如何轉化成雙向鏈表,需將中序遍歷部分添加前后指針
1.前指針開始置空,鏈接完后更新為當前節點,當前節點往下遞歸,再鏈接,如此下去直到結束
2.后指針如何鏈接?我們無法預知未來,若是穿越者就可,所以當遍歷到下一個節點時,將上一個節點(需判斷不為空時)的后指針指向當前節點,就完成了后指針鏈接的難題,中序遍歷最后節點的后指針一定為空。
注意:
InOrder函數傳參時prev要傳指針的引用,因為再遞歸過程中會不斷開辟新的棧幀,不傳引用沒辦法控制每個棧幀中prev相同,鏈接就會出問題

根據一棵樹的前序遍歷與中序遍歷構造二叉樹

在這里插入圖片描述

思路:
前序確定根節點位置,中序用來劃分區間

/*** 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) {}* };*/TreeNode* build(vector<int>& preorder, vector<int>& inorder,int& prei,int inbegin,int inend){if(inbegin>inend)return nullptr;//創建節點TreeNode*root=new TreeNode(preorder[prei]);//在中序容器中找到根節點來劃分區間//int rooti=prei;prei每次遞歸都會增加,所以在遞歸過程中可能讓rooti錯失根節點//位置,導致劃分區間出現問題,會導致數組越界問題int rooti=inbegin;while(rooti<inend){if(preorder[prei]==inorder[rooti])break;rooti++;}//劃分好區間[inbegin,rooti-1]rooti[rooti+1,inend]//按前序遍歷依次遞歸,鏈接節點prei++;root->left=build(preorder,inorder,prei,inbegin,rooti-1);root->right=build(preorder,inorder,prei,rooti+1,inend);return root;}
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i=0;TreeNode*root=build(preorder,inorder,i,0,inorder.size()-1);return root;}
};

1.結束條件:創建節點函數中當初下標大于尾下標時無法構建出區間,返回空節點
2.用前序vector和其下標prei來創建節點,第一次為根節點,后面prei不斷更新依次創建出前序遍歷中每個節點
3.通過循環比較來找出中序vector中根節點位置,從而劃分區間
4.通過遞歸調用按照前序遍歷依次鏈接每個節點,返回根節點。每進行一次遞歸,prei都要++,直到遍歷完前序vector,為確保每次遞歸新創建的棧幀中prei相同,參數要傳引用。

二叉樹的前序遍歷,非遞歸迭代實現

思路:

前序遍歷,最先訪問到的節點是左路節點,再訪問左路節點的右子樹。我們可以利用棧后進先出的特性來實現
1.創建一個vector來實現最終輸出,一個stack來實現遍歷操作,一個cur代替根節點進行遍歷
2.循環條件,當前節點cur和棧其中一個不為空。cur是訪問一棵樹的開始,先訪問左路節點,依次如棧,節點值也依次如vector
3.依次訪問左路節點的右子樹,創建top取棧頂元素,再pop掉,因為已經訪問過了,棧中剩余元素是未訪問的。利用子問題的方式訪問右子樹,將cur更新為右子樹,進行循環遍歷。

/*** 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> preorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*>st;TreeNode*cur=root;while(cur||!st.empty()){//訪問的開始,先訪問左子樹while(cur){v.push_back(cur->val);st.push(cur);cur=cur->left;}//訪問左子樹的右子樹TreeNode*top=st.top();st.pop();//訪問右子樹轉化為子問題cur=top->right;}return v;}
};

總結:

通過棧后進先出特性能確保從下往上依次訪問左子樹的右樹,滿足前序性質。本質還是遞歸的思想,不過用循環來實現。依次訪問左節點的右子樹,還是會將其轉化為先訪問左子樹,再訪問左子樹的右子樹的子問題

二叉樹中序遍歷,非遞歸迭代實現

與前序遍歷的非遞歸思路相同,只是左路節點的訪問時機不同
思路:
1.左路節點入棧 2.訪問左路節點及左路節點右子樹
本質:在遍歷左節點過程中先不入vector,從棧中取到一個節點,意味著這個節點的左子樹已經訪問完了,再把當前節點入vector

因為先遍歷左節點,最后肯定遇到空結束,代表最后節點左子樹為空,已經訪問完了,再取棧頂元素,然后pop掉,意味著當前節點的左子樹已訪問完,當前節點作為根節點入vector,再將當前節點更新為其右子樹,滿足了中序遍歷性質。再取棧頂元素,舊棧頂元素(上一次pop掉的)作為當前棧頂元素的左子樹已被訪問過并且已經入vector,如此循環往復直到遍歷完成。

/*** 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> inorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*>st;TreeNode*cur=root;while(cur||!st.empty()){//訪問的開始,先訪問左子樹while(cur){st.push(cur);cur=cur->left;}//訪問左子樹的右子樹TreeNode*top=st.top();st.pop();v.push_back(top->val);//訪問右子樹轉化為子問題cur=top->right;}return v;}
};

可看出與前序遍歷的非遞歸實現,僅僅是v.push_back(top->val);的執行順序不同,中序遍歷放在了取棧頂元素之后,而前序遍歷放在了遍歷左節點時直接訪問

二叉樹的后序遍歷 ,非遞歸迭代實現

按照 左子樹 右子樹 根的順序訪問,如何在訪問根節點前訪問右子樹呢?

采取比較的方式,容易理解和操作:
1.和中序遍歷一樣,先遍歷左節點入棧,等取棧頂元素后再訪問
2.如果當前節點的右子樹沒訪問過,上一個訪問的節點是左子樹的根
3.如果當前節點的右子樹已訪問過,上一個訪問的節點是右子樹的根

/*** 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> postorderTraversal(TreeNode* root) {vector<int> v;stack<TreeNode*>st;TreeNode*prev=nullptr;TreeNode*cur=root;while(cur||!st.empty()){//訪問的開始,先遍歷左子樹while(cur){st.push(cur);cur=cur->left;}TreeNode*top=st.top();//如果右子樹為或上一個訪問的節點為右子樹,代表//右子樹已訪問完if(top->right==nullptr||top->right==prev){prev=top;v.push_back(top->val);st.pop();}else{cur=top->right;}}return v;}
};

需要創建一個prev來保存上一個訪問過的節點,通過一個圖來分析感受一下
在這里插入圖片描述
1.先遍歷左節點,124依次入棧
2.取棧頂元素4,其左子樹為空相當于訪問過了,其右子樹為空也相當于訪問過了,直接將4入vector,將prev更新為當前top,然后pop
3.繼續取棧頂元素2,其左子樹4已訪問過,其右樹不為空,更新當前結點為其右樹,返回循環,劃分為子問題,56依次入棧,取棧頂元素6,其左子樹和右子樹為空相當于訪問過,直接將6入vector,然后pop。繼續取棧頂元素5,其左子樹6已訪問過,右子樹不為空,更新當前節點為其右子樹,如此循環。剩下部分分析省略,思路相同
4.按照如此方式就可以完成后序遍歷

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/bicheng/78184.shtml
繁體地址,請注明出處:http://hk.pswp.cn/bicheng/78184.shtml
英文地址,請注明出處:http://en.pswp.cn/bicheng/78184.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

RSUniVLM論文精讀

一些收獲&#xff1a; 1. 發現這篇文章的table1中&#xff0c;有CDChat ChangeChat Change-Agent等模型&#xff0c;也許用得上。等會看看有沒有源代碼。 摘要&#xff1a;RSVLMs在遙感圖像理解任務中取得了很大的進展。盡管在多模態推理和多輪對話中表現良好&#xff0c;現有模…

低空AI系統的合規化與標準化演進路徑

隨著AI無人機集群逐步參與城市空域治理、物流服務與公共安全作業&#xff0c;其系統行為不再是“技術封閉域”&#xff0c;而需接受法規監管、責任評估與接口協同的多方審查。如何將AI集群系統推向標準化、可接入、可審計的合規體系&#xff0c;成為未來空中交通演進的關鍵。本…

【金倉數據庫征文】從云計算到區塊鏈:金倉數據庫的顛覆性創新之路

目錄 一、引言 二、金倉數據庫概述 2.1 金倉數據庫的背景 2.2 核心技術特點 2.3 行業應用案例 三、金倉數據庫的產品優化提案 3.1 性能優化 3.1.1 查詢優化 3.1.2 索引優化 3.1.3 緩存優化 3.2 可擴展性優化 3.2.1 水平擴展與分區設計 3.2.2 負載均衡與讀寫分離 …

致遠oa部署

文章目錄 環境搭建項目構建 僅供學習使用 環境搭建 準備項目&#xff1a; https://pan.quark.cn/s/04a166575e94 https://pan.xunlei.com/s/VOOc1c9dBdLIuU8KKiqDa68NA1?pwdmybd# 官方文檔: https://open.seeyoncloud.com/v5devCTP/ 安裝時 mysql 數據庫可能出現字符集設置…

移遠通信智能模組助力東成“無邊界智能割草機器人“閃耀歐美市場

2025年4月21日&#xff0c;移遠通信宣布&#xff0c;旗下SC206E-EM智能模組已成功應用于江蘇東成電動工具有限公司旗下的DCK TERRAINA無邊界智能割草機器人。 這款智能模組高度集成計算、通信、定位等多元能力&#xff0c;以小型化、低功耗、實時性強和低成本等綜合優勢&#…

100.HTB-Meow

學習成果 在第一層&#xff0c;您將獲得網絡安全滲透測試領域的基本技能。您將首先學習如何匿名連接到各種服務&#xff0c;例如 FTP、SMB、Telnet、Rsync 和 RDP。接下來&#xff0c;您將發現 Nmap 的強大功能&#xff0c;Nmap 是一個有價值的工具&#xff0c;用于識別目標系統…

大廠面試-redis

前言 本章內容來自B站黑馬程序員java大廠面試題和小林coding 博主學習筆記&#xff0c;如果有不對的地方&#xff0c;海涵。 如果這篇文章對你有幫助&#xff0c;可以點點關注&#xff0c;點點贊&#xff0c;謝謝你&#xff01; 1.redis的使用場景 1.1 緩存 緩存穿透 在布…

【含文檔+PPT+源碼】基于SpringBoot+vue的疫苗接種系統的設計與實現

項目介紹 本課程演示的是一款 基于SpringBootvue的疫苗接種系統的設計與實現&#xff0c;主要針對計算機相關專業的正在做畢設的學生與需要項目實戰練習的 Java 學習者。 1.包含&#xff1a;項目源碼、項目文檔、數據庫腳本、軟件工具等所有資料 2.帶你從零開始部署運行本套系…

【Pandas】pandas DataFrame dot

Pandas2.2 DataFrame Binary operator functions 方法描述DataFrame.add(other)用于執行 DataFrame 與另一個對象&#xff08;如 DataFrame、Series 或標量&#xff09;的逐元素加法操作DataFrame.add(other[, axis, level, fill_value])用于執行 DataFrame 與另一個對象&…

Windows上Tomcat 11手動啟動startup.bat關閉shutdown.bat

發現tomcat11無法手動雙擊startup.bat和shutdown.bat進行開啟和關閉。雙擊startup.bat命令窗口一閃而過就是啟動失敗了&#xff0c;正常啟動成功是cmd命令窗口有全副的執行輸出且不關閉窗口。 解決方法如下&#xff1a;主要更改一個tomcat安裝目錄下的/conf/server.xml配置 1.…

7.9 Python+Click實戰:5步打造高效的GitHub監控CLI工具

Python+Click實戰:5步打造高效的GitHub監控CLI工具 GitHub Sentinel Agent 命令行界面開發實戰 關鍵詞:CLI 開發實踐、Click 框架、API 集成、命令行參數解析、錯誤處理機制 1. 命令行界面技術選型與架構設計 GitHub Sentinel 采用 Click + Requests 技術棧構建 CLI 工具,…

安全框架概述

Java中的安全框架通常是指解決Web應用安全問題的框架&#xff0c;如果開發Web應用時沒有使用安全框架&#xff0c;開發者需要自行編寫代碼增加Web應用安全性。自行實現Web應用的安全性并不容易&#xff0c;需要考慮不同的認證和授權機制、網絡關鍵數據傳輸加密等多方面的問題&a…

配置 C/C++ 語言智能感知(IntelliSense)的 c_cpp_properties.json 文件內容

配置 C/C 語言智能感知&#xff08;IntelliSense&#xff09;的 c_cpp_properties.json 文件內容 {"configurations": [{"name": "Linux","includePath": ["${workspaceFolder}/**","/opt/ros/humble/include/**&quo…

【安全掃描器原理】網絡掃描算法

【安全掃描器原理】網絡掃描算法 1.非順序掃描2.高速掃描 & 分布式掃描3.服務掃描 & 指紋掃描 1.非順序掃描 參考已有的掃描器&#xff0c;會發現幾乎所有的掃描器都無一例外地使用增序掃描&#xff0c;即對所掃描的端口自小到大依次掃描&#xff0c;殊不知&#xff0…

理解歐拉公式

1. 歐拉公式中的符號 歐拉公式 e i x cos ? x i sin ? x e^{ix}\cos xi\sin x eixcosxisinx當 x π x \pi xπ時 e i π 1 0 / / 歐拉恒等式 e^{i\:\pi}10 //歐拉恒等式 eiπ10//歐拉恒等式 e e e:自然對數的底 i i i:虛數&#xff0c; i 2 ? 1 i^2 -1 i2?1 cos…

HTML郵件背景圖兼容 Outlook

在 HTML 郵件中設置背景圖片時&#xff0c;Outlook&#xff08;尤其是桌面版的 Outlook for Windows&#xff09;經常不會正確顯示背景圖&#xff0c;這是因為outlook 是使用 Word 作為郵件渲染引擎&#xff0c;而不是標準的 HTML/CSS 渲染方式。 推薦的解決方案&#xff1a;使…

杰理ac792開發板按鍵不起效果

按鍵想要起效果需要把UI給注釋掉&#xff0c;排查了半天

Kubernetes 常用運維命令整理

目錄 Kubernetes 常用運維命令整理一、集群管理二、Pod 和容器管理三、Deployment 和應用管理四、Service 和網絡管理五、存儲管理六、ConfigMap 和 Secret 管理七、資源使用與監控八、調度和容錯九、Role 和權限管理十、清理資源 總結 Kubernetes 常用運維命令整理 Kubernete…

在 Debian 12 中恢復被刪除的 smb.conf 配置文件

https://forum.ubuntu.com.cn/viewtopic.php?t494763 本文結合ai輸出&#xff0c;內容中有些錯誤&#xff0c;但確實解決了我的問題&#xff0c;我采取保留完整輸出的方式摘錄。 在 Debian 12 中恢復被刪除的 smb.conf 配置文件&#xff0c;需結合 dpkg 和 ucf&#xff08;Upd…

GB2312/GBK是字符集嗎

GB2312/GBK 是字符集嗎&#xff1f; 是的&#xff0c;GB2312 和 GBBK 既是字符集&#xff08;Character Set&#xff09;&#xff0c;也是編碼方式&#xff08;Encoding&#xff09;。它們不僅定義了可表示的字符范圍&#xff0c;還規定了這些字符在計算機中的二進制存儲格式。…