在上節(jié)的基礎(chǔ)上奸柬，本節(jié)我們將繼續(xù)匯總一些 LeetCode 有關(guān)二叉樹的題。
接著上節(jié)则酝，我們繼續(xù)匯總二叉樹相關(guān)的例題惠奸。
所有題均來自于leetcode。
二叉樹剪枝
給定二叉樹根結(jié)點(diǎn) root 桨螺，此外樹的每個(gè)結(jié)點(diǎn)的值要么是 0宾符，要么是 1。
返回移除了所有不包含 1 的子樹的原二叉樹彭谁。
( 節(jié)點(diǎn) X 的子樹為 X 本身吸奴，以及所有 X 的后代。)
移除的條件是這個(gè)子樹含有0缠局，遞歸左右子樹则奥，如果滿足條件，對(duì)應(yīng)的指針域賦值為空即可狭园。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* pruneTree(TreeNode* root) {
if(fun(root)){
return root;
}else{
return NULL;
}
}
bool fun(TreeNode* tree){
if(tree==NULL){
return false;
}
bool l=fun(tree->left);
bool r=fun(tree->right);
if(!l){
tree->left=NULL;
}
if(!r){
tree->right=NULL;
}
return tree->val==1||l||r;
}
};
最長同值路徑
給定一個(gè)二叉樹读处，找到最長的路徑，這個(gè)路徑中的每個(gè)節(jié)點(diǎn)具有相同值唱矛。 這條路徑可以經(jīng)過也可以不經(jīng)過根節(jié)點(diǎn)罚舱。
注意：兩個(gè)節(jié)點(diǎn)之間的路徑長度由它們之間的邊數(shù)表示。
在遞歸過程中绎谦，如果其左(右)子樹的節(jié)點(diǎn)域等于根節(jié)點(diǎn)的節(jié)點(diǎn)域管闷，說明這可能是一條路徑，遞歸左右子樹窃肠，同時(shí)記錄路徑長度包个。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int res;
int longestUnivaluePath(TreeNode* root) {
res=0;
fun(root);
return res;
}
int fun(TreeNode* root){
if(root==NULL){
return 0;
}
int l=fun(root->left);
int r=fun(root->right);
int ll=0,rr=0;
if(root->left!=NULL && root->left->val==root->val){
ll+=l+1;
}
if(root->right!=NULL && root->right->val==root->val){
rr+=r+1;
}
res=max(res,rr+ll);
return max(ll,rr);
}
};
二叉樹最大寬度
給定一個(gè)二叉樹，編寫一個(gè)函數(shù)來獲取這個(gè)樹的最大寬度冤留。樹的寬度是所有層中的最大寬度碧囊。這個(gè)二叉樹與滿二叉樹（full binary tree）結(jié)構(gòu)相同，但一些節(jié)點(diǎn)為空纤怒。
每一層的寬度被定義為兩個(gè)端點(diǎn)（該層最左和最右的非空節(jié)點(diǎn)糯而，兩端點(diǎn)間的null節(jié)點(diǎn)也計(jì)入長度）之間的長度。
bfs做法泊窘，只不過稍微有一點(diǎn)點(diǎn)區(qū)別熄驼，我們需要使用雙端隊(duì)列像寒，入節(jié)點(diǎn)方式略有不同。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int widthOfBinaryTree(TreeNode* root) {
int ans=0;
if(!root){
return ans;
}
TreeNode* tmp=nullptr;
deque<TreeNode*> d;
d.push_back(root);
while(!d.empty()){
//判斷隊(duì)列是否為空
while(!d.empty() && !d.front()){
d.pop_front();
}
while(!d.empty() && !d.back()){
d.pop_back();
}
int n=d.size();
if(!n){
break;
}
ans=max(ans,n);
while(n--){
tmp=d.front();
d.pop_front();
d.push_back(tmp==NULL ? NULL:tmp->left);
d.push_back(tmp==NULL ? NULL:tmp->right);
}
}
return ans;
}
};
根據(jù)二叉樹創(chuàng)建字符串
你需要采用前序遍歷的方式谜洽，將一個(gè)二叉樹轉(zhuǎn)換成一個(gè)由括號(hào)和整數(shù)組成的字符串萝映。
空節(jié)點(diǎn)則用一對(duì)空括號(hào) "()" 表示吴叶。而且你需要省略所有不影響字符串與原始二叉樹之間的一對(duì)一映射關(guān)系的空括號(hào)對(duì)阐虚。
本題需要考慮遞歸過程中左右子樹的處理情況，解決好這個(gè)問題蚌卤，就不難了实束。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
string tree2str(TreeNode* t) {
if(!t){
return "";
}
if(!t->left&&!t->right){
return to_string(t->val) +"";
}
if(!t->right){
return to_string(t->val)+"("+tree2str(t->left)+")";
}
return to_string(t->val)+"("+tree2str(t->left)+")("+tree2str(t->right)+")";
}
};
