在上节的基础上，本节我们将继续汇总一些 LeetCode 有关二叉树的题。
接着上节，我们继续汇总二叉树相关的例题。
所有题均来自于leetcode。
二叉树展开为链表
给定一个二叉树，原地将它展开为链表。
例如，给定二叉树
我们使用一个队列保存该树前序遍历的结果，之后可以先弹出队列的第一个节点temp，使其左子树为空，右子树指向剩余队列的头部元素node，将node赋值给temp，循环该操作。
程序如下：
/**
* 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);
}
}
};
填充每个节点的下一个右侧节点指针
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
提示：
你只能使用常量级额外空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
这个题可以使用层序遍历的方式，使用队列保存每一层的节点，当为最后一个节点时，使其next为空，否则当前节点的next指向剩余队列的第一个元素，循环该过程，同时保存下一层节点。
程序如下:
/*
// 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;
}
};
事后发现这个题的方法也可以用到填充每个节点的下一个右侧节点指针 II上，那这个题就不介绍了。
二叉树的右视图
给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
使用层序遍历的方式，保存每一层的最后一个节点的值。
程序如下：
/**
* 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;
}
};
二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉树中。
先处理其中一个节点作为两个节点的父亲节点情况，当root为q或者p时，此时root为它们的祖先。
否则继续递归左右子树，左右子树有一者为空，返回非空子树；都为空返回根节点。
程序如下：
/**
* 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;
}
};
二叉树的直径
给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。
示例 :
给定二叉树
1
/ \
2 3
/ \
4 5
返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
注意：两结点之间的路径长度是以它们之间边的数目表示。
求树深度的变形，递归过程中保存左右子树的最大深度即可。
程序如下：
/**
* 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;
}
};
另一个数的子树
给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
这个题一方面可以保存其遍历节点继续判断，另一方面也可以递归判断，这里我使用的是前者。
保存遍历结果时，要注意保存节点时不能只保存其数据域，还得记录每个节点左右子树的情况，即左右子树为空时，也要将其作为一种结果保存进去，保存的方式可以使用容器，也可以使用字符串，要注意c++对字符串的判断方式。
string::size_type idx = res1.find(res2);
if(idx==string::npos){
return false;
}else{
return true;
}
根据其返回值idx来判断，若存在会返回相同串的起始索引位置。
程序如下：
/**
* 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);
}
};
合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
递归过程中，若有一方节点为空，返回非空节点；都不为空，对应节点值可以加到其中一个子树上，之后递归合并左右子树。
程序如下：
/**
* 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;
}
};
