在上節(jié)的基礎(chǔ)上泞辐，本節(jié)我們將繼續(xù)匯總一些 LeetCode 有關(guān)二叉樹的題笔横。
接著上節(jié)，我們繼續(xù)匯總二叉樹相關(guān)的例題铛碑。
所有題均來自于leetcode狠裹。
二叉樹展開為鏈表
給定一個(gè)二叉樹虽界，原地將它展開為鏈表汽烦。
例如，給定二叉樹
我們使用一個(gè)隊(duì)列保存該樹前序遍歷的結(jié)果莉御，之后可以先彈出隊(duì)列的第一個(gè)節(jié)點(diǎn)temp撇吞，使其左子樹為空，右子樹指向剩余隊(duì)列的頭部元素node礁叔，將node賦值給temp牍颈，循環(huá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:
queue<TreeNode*> q;
void flatten(TreeNode* root) {
if(root==NULL){
return ;
}
helper(root);
TreeNode* temp = q.front();
q.pop();
while(!q.empty()){
TreeNode* node = q.front();
q.pop();
temp->left=NULL;
temp->right=node;
temp = node;
}
}
void helper(TreeNode* root){
if(root!=NULL){
q.push(root);
helper(root->left);
helper(root->right);
}
}
};
填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針
給定一個(gè)完美二叉樹琅关，其所有葉子節(jié)點(diǎn)都在同一層煮岁，每個(gè)父節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)。二叉樹定義如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個(gè) next 指針，讓這個(gè)指針指向其下一個(gè)右側(cè)節(jié)點(diǎn)画机。如果找不到下一個(gè)右側(cè)節(jié)點(diǎn)冶伞，則將 next 指針設(shè)置為 NULL。
初始狀態(tài)下步氏，所有 next 指針都被設(shè)置為 NULL响禽。
提示：
你只能使用常量級(jí)額外空間。
使用遞歸解題也符合要求荚醒，本題中遞歸程序占用的椨罄啵空間不算做額外的空間復(fù)雜度。
這個(gè)題可以使用層序遍歷的方式界阁，使用隊(duì)列保存每一層的節(jié)點(diǎn)侯繁，當(dāng)為最后一個(gè)節(jié)點(diǎn)時(shí)，使其next為空铺董，否則當(dāng)前節(jié)點(diǎn)的next指向剩余隊(duì)列的第一個(gè)元素巫击，循環(huán)該過程，同時(shí)保存下一層節(jié)點(diǎn)精续。
程序如下:
/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
Node* connect(Node* root) {
if(root==NULL){
return root;
}
queue<Node*> q;
q.push(root);
while(!q.empty()){
int n = q.size();
for(int i=1;i<=n;i++){
Node* p=q.front();
q.pop();
if(i==n){
p->next=NULL;
}else{
p->next=q.front();
}
if(p->left){
q.push(p->left);
}
if(p->right){
q.push(p->right);
}
}
}
return root;
}
};
事后發(fā)現(xiàn)這個(gè)題的方法也可以用到填充每個(gè)節(jié)點(diǎn)的下一個(gè)右側(cè)節(jié)點(diǎn)指針 II上坝锰，那這個(gè)題就不介紹了。
二叉樹的右視圖
給定一棵二叉樹重付，想象自己站在它的右側(cè)顷级，按照從頂部到底部的順序，返回從右側(cè)所能看到的節(jié)點(diǎn)值确垫。
使用層序遍歷的方式弓颈，保存每一層的最后一個(gè)節(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:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if(root==NULL){
return res;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
int n=q.size();
for(int i=1;i<=n;i++){
TreeNode* node =q.front();
q.pop();
if(i==n){
res.push_back(node->val);
}
if(node->left){
q.push(node->left);
}
if(node->right){
q.push(node->right);
}
}
}
return res;
}
};
二叉樹的最近公共祖先
給定一個(gè)二叉樹, 找到該樹中兩個(gè)指定節(jié)點(diǎn)的最近公共祖先删掀。
百度百科中最近公共祖先的定義為：“對(duì)于有根樹 T 的兩個(gè)結(jié)點(diǎn) p翔冀、q，最近公共祖先表示為一個(gè)結(jié)點(diǎn) x披泪，滿足 x 是 p纤子、q 的祖先且 x 的深度盡可能大（一個(gè)節(jié)點(diǎn)也可以是它自己的祖先）】钇保”
例如控硼，給定如下二叉樹: root = [3,5,1,6,2,0,8,null,null,7,4]
說明:
- 所有節(jié)點(diǎn)的值都是唯一的。
- p艾少、q 為不同節(jié)點(diǎn)且均存在于給定的二叉樹中卡乾。
先處理其中一個(gè)節(jié)點(diǎn)作為兩個(gè)節(jié)點(diǎn)的父親節(jié)點(diǎn)情況，當(dāng)root為q或者p時(shí)缚够，此時(shí)root為它們的祖先幔妨。
否則繼續(xù)遞歸左右子樹鹦赎，左右子樹有一者為空，返回非空子樹误堡；都為空返回根節(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:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root||p==root||q==root){
return root;
}
TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);
if(!left){
return right;
}
if(!right){
return left;
}
if(left && right){
return root;
}
return NULL;
}
};
二叉樹的直徑
給定一棵二叉樹，你需要計(jì)算它的直徑長(zhǎng)度埂伦。一棵二叉樹的直徑長(zhǎng)度是任意兩個(gè)結(jié)點(diǎn)路徑長(zhǎng)度中的最大值煞额。這條路徑可能穿過根結(jié)點(diǎn)。
示例 :
給定二叉樹
1
/ \
2 3
/ \
4 5
返回 3, 它的長(zhǎng)度是路徑 [4,2,1,3] 或者 [5,2,1,3]沾谜。
注意：兩結(jié)點(diǎn)之間的路徑長(zhǎng)度是以它們之間邊的數(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 ans =1;
int diameterOfBinaryTree(TreeNode* root) {
helper(root);
return ans-1;
}
int helper(TreeNode* root){
if(root==NULL){
return 0;
}
int l = helper(root->left);
int r= helper(root->right);
ans=max(ans,l+r+1);
return max(l,r)+1;
}
};
另一個(gè)數(shù)的子樹
給定兩個(gè)非空二叉樹 s 和 t婚温，檢驗(yàn) s 中是否包含和 t 具有相同結(jié)構(gòu)和節(jié)點(diǎn)值的子樹。s 的一個(gè)子樹包括 s 的一個(gè)節(jié)點(diǎn)和這個(gè)節(jié)點(diǎn)的所有子孫媳否。s 也可以看做它自身的一棵子樹栅螟。
這個(gè)題一方面可以保存其遍歷節(jié)點(diǎn)繼續(xù)判斷，另一方面也可以遞歸判斷篱竭，這里我使用的是前者力图。
保存遍歷結(jié)果時(shí)，要注意保存節(jié)點(diǎn)時(shí)不能只保存其數(shù)據(jù)域掺逼，還得記錄每個(gè)節(jié)點(diǎn)左右子樹的情況吃媒，即左右子樹為空時(shí)，也要將其作為一種結(jié)果保存進(jìn)去吕喘，保存的方式可以使用容器赘那，也可以使用字符串，要注意c++對(duì)字符串的判斷方式氯质。
string::size_type idx = res1.find(res2);
if(idx==string::npos){
return false;
}else{
return true;
}
根據(jù)其返回值idx來判斷募舟，若存在會(huì)返回相同串的起始索引位置。
程序如下：
/**
* 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:
bool isSubtree(TreeNode* s, TreeNode* t) {
string res1=helper(s,true);
string res2=helper(t,true);
string::size_type idx=res1.find(res2);
if(idx==string::npos){
return false;
}else{
return true;
}
}
string helper(TreeNode* root,bool sign){
if(!root){
if(sign){
return "l";
}else{
return "r";
}
}
return "#"+to_string(root->val)+helper(root->left,true)+helper(root->right,false);
}
};
合并二叉樹
給定兩個(gè)二叉樹闻察，想象當(dāng)你將它們中的一個(gè)覆蓋到另一個(gè)上時(shí)拱礁，兩個(gè)二叉樹的一些節(jié)點(diǎn)便會(huì)重疊。
你需要將他們合并為一個(gè)新的二叉樹蜓陌。合并的規(guī)則是如果兩個(gè)節(jié)點(diǎn)重疊觅彰，那么將他們的值相加作為節(jié)點(diǎn)合并后的新值吩蔑，否則不為 NULL 的節(jié)點(diǎn)將直接作為新二叉樹的節(jié)點(diǎn)钮热。
遞歸過程中，若有一方節(jié)點(diǎn)為空烛芬，返回非空節(jié)點(diǎn)隧期；都不為空飒责，對(duì)應(yīng)節(jié)點(diǎn)值可以加到其中一個(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:
TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
if(!t1){
return t2;
}
if(!t2){
return t1;
}
t1->val+=t2->val;
t1->left=mergeTrees(t1->left,t2->left);
t1->right=mergeTrees(t1->right,t2->right);
return t1;
}
};
