首先我們先回憶我們過(guò)去學(xué)的二叉樹和最近學(xué)的二叉搜索樹,來(lái)完成下面的題目:

606. 根據(jù)二叉樹創(chuàng)建字符串

這道題屬于與基礎(chǔ)題,首先我們觀察輸入輸出樣例可以得到如果root->left為空,root->right不為空時(shí),我們的空格仍然需要保留,如果當(dāng)前節(jié)點(diǎn)有兩個(gè)孩子，那我們?cè)谶f歸時(shí)，需要在兩個(gè)孩子的結(jié)果外都加上一層括號(hào)；如果當(dāng)前節(jié)點(diǎn)沒(méi)有孩子，那我們不需要在節(jié)點(diǎn)后面加上任何括號(hào)；如果當(dāng)前節(jié)點(diǎn)只有左孩子，那我們?cè)谶f歸時(shí)，只需要在左孩子的結(jié)果外加上一層括號(hào)，而不需要給右孩子加上任何括號(hào)；

代碼示例:

class Solution {
public:string tree2str(TreeNode* root) {string str;if(root==nullptr){return str;}str+=to_string(root->val);if(root->left||root->right){   str+='(';str+=tree2str(root->left);str+=')';}if(root->right){str+='(';str+=tree2str(root->right);str+=')';}return str;}
};

102. 二叉樹的層序遍歷

我們可以通過(guò)隊(duì)列來(lái)解決

核心思想:我們?cè)趯有虮闅v過(guò)程中，增加一-個(gè)levelSize,記錄每層的數(shù)據(jù)個(gè)數(shù)，樹不為空的情況下,第1層levelSize=1,循環(huán)控制，第1層出完了，第2層就都進(jìn)隊(duì)列了，隊(duì)列中size就是第2層的數(shù)據(jù)個(gè)數(shù)。以此內(nèi)推,假設(shè)levelSize為第n層的數(shù)據(jù)個(gè)數(shù)，因?yàn)閷有虮闅v思想為當(dāng)前層結(jié)點(diǎn)出隊(duì)列，帶入下一層結(jié)點(diǎn)(也就是子結(jié)點(diǎn)),循環(huán)控制第n層數(shù)據(jù)出完了，那么第n+1結(jié)點(diǎn)都進(jìn)隊(duì)列了，隊(duì)列size,就是下一層的levelSize。

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> vv;queue<TreeNode*> q;int levelsize=0;if(root){q.push(root);levelsize=1;}while(levelsize){vector<int> v;while(levelsize--){TreeNode*front=q.front();q.pop();v.push_back(front->val);if(front->left)q.push(front->left);if(front->right)q.push(front->right);}levelsize=q.size();vv.push_back(v);}return vv;}
};

107. 二叉樹的層序遍歷 II

上題我們搞完了,這題我們其實(shí)有個(gè)很簡(jiǎn)單的辦法,我們把上題的代碼賦值過(guò)來(lái)直接逆置即可

代碼示例:

class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {vector<vector<int>> vv;queue<TreeNode*> q;int levelsize=0;if(root){q.push(root);levelsize=1;}while(levelsize){vector<int> v;while(levelsize--){TreeNode*front=q.front();q.pop();v.push_back(front->val);if(front->left)q.push(front->left);if(front->right)q.push(front->right);}vv.push_back(v);levelsize=q.size();}reverse(vv.begin(),vv.end());return vv;}
};

236. 二叉樹的最近公共祖先

本題思路有二,我們一個(gè)一個(gè)來(lái)講

方法一：遞歸

首先我們對(duì)于題意進(jìn)行分析,我們可以知道公共祖先分為以下幾種情況:

1.p或q在root節(jié)點(diǎn)處,此時(shí)最近的公共祖先就是root

2.p和q分別分布在root的左右子樹,此時(shí)公共祖先就是root

3.p和q分布在root的同一子樹,此時(shí)我們可以把該子節(jié)點(diǎn)看作root,繼續(xù)判斷。

代碼實(shí)現(xiàn)：

class Solution {
public:bool Intree(TreeNode* t,TreeNode* x){if(!t){return false;}return x==t||Intree(t->left,x)||Intree(t->right,x);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==p||root==q){return root;}bool pinleft=Intree(root->left,p);bool pinright=!pinleft;bool qinleft=Intree(root->left,q);bool qinright=!qinleft;if((pinleft&&qinright)||(pinright&&qinleft)){return root;}else if(pinleft&&qinleft){return lowestCommonAncestor(root->left,p,q);}else{return lowestCommonAncestor(root->right,p,q);}}
};

下面我們來(lái)講講第二種方法

思路2:如果能求出兩個(gè)結(jié)點(diǎn)到根的路徑，那么就可以轉(zhuǎn)換為鏈表相交問(wèn)題。如:?6到根3的路徑為6->5->3,?4到根3的路徑為4->2->5->3,那么看做兩個(gè)鏈表找交點(diǎn)，交點(diǎn)5就是最近公共祖先。

代碼示例:

class Solution {
public:bool GetPath(TreeNode* root,TreeNode* x,stack<TreeNode*>& path){if(root==nullptr)return false;path.push(root);if(root==x)return true;if(GetPath(root->left,x,path))return true;if(GetPath(root->right,x,path))return true;path.pop();return false;}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> ppath,qpath;GetPath(root,p,ppath);GetPath(root,q,qpath);//確定長(zhǎng)度while(ppath.size()!=qpath.size()){//長(zhǎng)的先if(ppath.size()>qpath.size()){ppath.pop();}else{qpath.pop();}}//找交點(diǎn)while(ppath.top()!=qpath.top()){ppath.pop();qpath.pop();}//輸出交點(diǎn)return ppath.top();}
};

JZ36?二叉搜索樹與雙向鏈表

這題在我們學(xué)完二叉搜索樹之后大家應(yīng)該覺得不難吧,核心思想:中序遍歷

代碼示例:

#include <cstddef>
class Solution {
public:TreeNode* head=nullptr;TreeNode* cur=nullptr;TreeNode* Convert(TreeNode* pRootOfTree) {if(pRootOfTree==nullptr)return nullptr;Convert(pRootOfTree->left);if(cur==nullptr){head=pRootOfTree;cur=pRootOfTree;}else {cur->right=pRootOfTree;pRootOfTree->left=cur;cur=pRootOfTree;}Convert(pRootOfTree->right);return head;}
};

105. 從前序與中序遍歷序列構(gòu)造二叉樹

本題咋一看很簡(jiǎn)單,仔細(xì)一看好像有點(diǎn)難,但是一看提示,瞬間就來(lái)了思路,其實(shí)很簡(jiǎn)單是不是.

我的思路:根據(jù)前序確定根，然后再中序中確定根所處的位置，分割兩個(gè)區(qū)間，然后遞歸即可。，遞歸截止的條件為當(dāng)左右不構(gòu)成區(qū)間。

代碼示例:

/*** 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: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=inbegin;while(rooti<=inend){if(preorder[prei] ==inorder[rooti])break;elserooti++;}prei++;root->left=build(preorder,inorder,prei,inbegin,rooti-1);root->right=build(preorder,inorder,prei,rooti+1,inend);return root;}TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {int i=0;return build(preorder,inorder,i,0,inorder.size()-1);}
};

106. 從中序與后序遍歷序列構(gòu)造二叉樹

這題是上一題的兄弟題,我們直接上代碼了,不懂的再想想,畫畫遞歸展開圖

/*** 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:TreeNode* build(vector<int>& inorder, vector<int>& postorder,int& posti,int inbegin,int inend){if(inbegin>inend)return nullptr;TreeNode* newnode=new TreeNode(postorder[posti]);int inpos=inbegin;while(inpos<=inend){if(postorder[posti]==inorder[inpos]){break;}inpos++;}posti--;newnode->right = build(inorder,postorder,posti,inpos+1,inend);newnode->left = build(inorder,postorder,posti,inbegin,inpos-1);return newnode;}TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {int i=postorder.size()-1;return build(inorder,postorder,i,0,inorder.size()-1);}
};