[TOC]
一、二叉树的序列化和反序列化
剑指 Offer 37. 序列化二叉树（困难难度）
297. 二叉树的序列化与反序列化（困难难度）
二叉树的序列化：输入一个二叉树，输出其层序遍历输出的字符串
二叉树的反序列化：输入一个字符串，输出其构造的二叉树
点评
二叉树的序列化有先序、中序、后序和层序，但是二叉树的反序列化不支持中序遍历（无法确定根节点位置）。
基于先序遍历的序列化和反序列化：
//序列化
string serialize(TreeNode* root){
string str="";
dfs(root,str);
return str;
}
void dfs(TreeNode* root,string& str){
if(root==nullptr){
str+="null,";
return;
}
str+=to_string(root->val)+",";
dfs(root->left,str);
dfs(root->right,str);
}
// 反序列化
TreeNode* deserialize(string data){
if(data.length()==0) return nullptr;
// 切割字符串
vector<string> str;
stringstream ss(data);
string t;
while(getline(ss,t,',')){
str.push_back(t);
}
// 构造二叉树
return dedfs(str,0);
}
TreeNode* dedfs(vector<string>& nodes，int i){
// 终止条件
if(i>=nodes.size()) return nullptr;
// 处理节点
if(nodes[i]=="null") return nullptr;
TreeNode* root=new TreeNode(stoi(nodes[i]));
i++;
// 递归搜索
root->left=dedfs(nodes,i);
root->right=dedfs(nodes,i);
return root;
}
基于层序遍历的序列化和反序列化：
string serialize(TreeNode* root) {
if(root==nullptr) return "";
string res="";
queue<TreeNode*> que;
que.push(root);
while(!que.empty()){
// 出栈
TreeNode* cur=que.front();
que.pop();
// 处理
if(cur==nullptr) res+="null,";
else{
res+=to_string(cur->val)+",";
// 入栈
que.push(cur->left);
que.push(cur->right);
}
}
return res;
}
TreeNode* deserialize(string data) {
if(data.length()==0) return nullptr;
// 切割字符串
vector<string> str;
stringstream ss(data);
string t;
while(getline(ss,t,',')){
str.push_back(t);
}
// 构建二叉树
queue<TreeNode*> que;
if(str[0]=="null") return nullptr;
TreeNode* root=new TreeNode(stoi(str[0]));
que.push(root);
for(int i=1;i<str.size();){
// 获取根节点
TreeNode* cur=que.front();
que.pop();
// 添加左节点
if(str[i]=="null") cur->left=nullptr;
else{
cur->left=new TreeNode(stoi(str[i]));
que.push(cur->left);
}
++i;
// 添加右节点
if(str[i]=="null") cur->right=nullptr;
else{
cur->right=new TreeNode(stoi(str[i]));
que.push(cur->right);
}
++i;
}
return root;
}
大
二、求二叉树的路径
257. 二叉树的所有路径（简单难度）
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
class Solution {
public:
vector<string> res;
void dfs(TreeNode* root,string path){
// 如果节点为空,返回
if(root==nullptr) return;
path+=to_string(root->val);//添加当前节点
//如果是叶子节点,说明一条路径结束,递归返回
if(root->left==nullptr&&root->right==nullptr){
res.push_back(path);
return;
}
if(root->left){
dfs(root->left,path+"->");
}
// 进入该节点，尝试搜索右节点
if(root->right){
dfs(root->right,path+"->");
}
}
vector<string> binaryTreePaths(TreeNode* root) {
dfs(root, "");
return res;
}
};
129. 求根节点到叶节点数字之和（中等难度）
剑指 Offer II 049. 从根节点到叶节点的路径数字之和（中等难度）
class Solution {
public:
vector<string> res;
void dfs(TreeNode* root,string path){
// 如果节点为空,返回
if(root==nullptr) return;
path+=to_string(root->val);//添加当前节点
// 如果是叶节点就是一条路径
if(root->left==nullptr&&root->right==nullptr){
res.push_back(path);
return;
}
// 进入该节点，尝试搜索左节点
if(root->left)dfs(root->left,path);
// 进入该节点，尝试搜索右节点
if(root->right)dfs(root->right,path);
}
int sumNumbers(TreeNode* root) {
dfs(root,"");
int sum=0;
for(string s:res){
sum+=stoi(s);
}
return sum;
}
};
124. 二叉树中的最大路径和（困难难度）
路径定义为从树中的任意节点出发，父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ，返回其 最大路径和 。
点评：
该题的难点在于路径的方向不固定，起点可以是任意节点，终点也可以说任意节点，然后返回路径和。
传统的二叉树的路径一般是从根节点到叶节点。
那么如何求任意节点到任意节点的最大路径和呢？
我们考虑一个最简单的二叉树，left表示左节点为根节点的子树的最大路径和，right表示右节点为根节点的子树的最大路径和。
那么对于root根的二叉树来讲，其形成的路径可以能有：
left-root-right（条件：left>0,right>0）
left-root（条件：left>0,right<=0）
root-right（条件：left<=0,right>0）
root（条件：left<=0,right<=0）
假设我们的递归函数dfs()返回以根节点root为子树的最大路径和，那么
int left=dfs(node->left);
int right=dfs(node->left);
class Solution {
public:
int maxSum = INT_MIN;// 记录的最大值
// 返回以node为根的左右子树中的最大和
int dfs(TreeNode* node) {
// 如果节点为空，返回
if (node == nullptr) return 0;
// 进入该节点
// 该节点尝试向左,left表示左子树最大的路径和，最小为0，如果设为0则放弃左子树为路径
int left = max(0, dfs(node->left));
// 该节点尝试向右，right表示右子树最大的路径和，最小为0，如果设为0则放弃左子树为路径
int right = max(0, dfs(node->right));
//假如以left-root-left为路径，得到路径和：
int priceNewpath = node->val + left + right;
// 如果该路径和最大则记录
maxSum = max(maxSum, priceNewpath);
// 该节点最终选择左还是右取决于左右子节点的最大贡献值
return max(node->val+left, node->val+right);
}
int maxPathSum(TreeNode* root) {
dfs(root);
return maxSum;
}
};
113. 路径总和 II
剑指 Offer 34. 二叉树中和为某一值的路径
class Solution {
public:
vector<vector<int>> result;
vector<int> path;
// 递归函数不需要返回值，因为我们要遍历整个树
void traversal(TreeNode* cur, int count) {
// 如果是叶子节点，且为0,添加到结果中并返回
if (!cur->left && !cur->right && count == 0) {
result.push_back(path);
return;
}
// 如果是叶子节点，不为0,直接返回
if (!cur->left && !cur->right) return ;
// 如果是左节点存在，递归左节点
if (cur->left) {
path.push_back(cur->left->val);
count -= cur->left->val;
traversal(cur->left, count); // 递归
count += cur->left->val; // 回溯
path.pop_back(); // 回溯
}
// 如果右节点存在，递归右节点
if (cur->right) { // 右 （空节点不遍历）
path.push_back(cur->right->val);
count -= cur->right->val;
traversal(cur->right, count); // 递归
count += cur->right->val; // 回溯
path.pop_back(); // 回溯
}
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
if (root == NULL) return result;
path.push_back(root->val); // 把根节点放进路径
traversal(root, targetSum - root->val);
return result;
}
};
437. 路径总和 III（中等难度）
方法一：递归法
class Solution {
public:
// 查找包含root节点并且和为sum的路径个数
int findPath(TreeNode* root,int sum){
int result=0;
if(root==nullptr) return result;
// 如果加上root，和满足则结果+1
if(sum==root->val) result+=1;
// 查找包含root左节点
result+=findPath(root->left,sum-root->val);
// 查找包含root右节点
result+=findPath(root->right,sum-root->val);
return result;
}
// 查找包含root/不包含root并且和为targetSum的路径个数
int pathSum(TreeNode* root, int targetSum) {
int result=0;
if(root==nullptr) return result;
result+=findPath(root,targetSum);// 查找包含root节点并且和为sum的路径个数
result+=pathSum(root->left,targetSum);// 查找包含root节点并且和为sum的路径个数
result+=pathSum(root->right,targetSum);
return result;
}
};
方法二：前缀和+递归法
class Solution {
public:
unordered_map<long long, int> dict; //<[0,b]的前缀和，出现次数>
int res = 0;
// pathSum：[a,root]的目标和;curSum：[0,root]的前缀和
void dfs(TreeNode* root,int pathSum,int curSum){
if (root == nullptr) return;
curSum += root->val; //当前节点的前缀和[0,b]
// [0,b]的前缀和-[a,b]的前缀和=[0,a-1]的前缀和，哈希表中是否存在
if (dict.count(curSum - pathSum)){
res += dict[curSum - pathSum];//
}
// 将[0,b]的前缀和存入哈希表，遍历是否存在满足要求的子树
dict[curSum]++;
dfs(root->left,pathSum, curSum);//查看是否存在root的左节点的
dfs(root->right,pathSum, curSum);
// 当子树结束时，应当把子树从哈希表中移除 (回溯：将一切复原，然后结束)。
dict[curSum]--;
}
// 查找包含root/不包含root并且和为targetSum的路径个数
int pathSum(TreeNode* root, int targetSum) {
// 注意 前缀和中, [a, b] = [0, b] - [0, a-1] 。
// 对于包含根节点的路径，是无法找到 a-1 的。所以需要一个虚拟根节点。
dict[0] = 1;
dfs(root,targetSum, 0); //targetSum视为[a,b]区间的和
return res;
}
};
404. 左叶子之和（简单难度）
class Solution {
public:
int preOrder(TreeNode* root,bool isleft){
int result=0;
// 如果是空节点，返回0
if(root==NULL) return 0;
// 如果是左叶子，返回其值
if(isleft&&root->left==NULL&&root->right==NULL) return root->val;
result+=preOrder(root->left,true);// 递归左节点
result+=preOrder(root->right,false);// 递归右节点
return result;
}
int sumOfLeftLeaves(TreeNode* root) {
return preOrder(root,false);
}
};
863. 二叉树中所有距离为 K 的结点（中等难度）
class Solution {
unordered_map<int, TreeNode*> parents;// 当前节点值-父节点
void findParents(TreeNode* node) {
if(node==nullptr) return;
if (node->left) {
parents[node->left->val] = node;//最节点的父节点是node
findParents(node->left);
}
if (node->right) {
parents[node->right->val] = node;//右节点的父节点是node
findParents(node->right);
}
}
vector<int> ans;
void findAns(TreeNode* node, TreeNode* from, int depth, int k) {
// 如果当前节点为空，返回
if (node == nullptr) return;
// 如果当前深度==k，返回并添加结果
if (depth == k) {
ans.push_back(node->val);
return;
}
// 搜索3个方向，from是搜索来源方向
if (node->left != from) findAns(node->left, node, depth + 1, k);// 左节点
if (node->right != from) findAns(node->right, node, depth + 1, k);// 右节点
if (parents[node->val] != from) findAns(parents[node->val], node, depth + 1, k);// 父节点
}
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
// 从root出发 DFS，记录每个结点的父结点
findParents(root);
// 从 target 出发 DFS，寻找所有深度为 k 的结点
findAns(target, nullptr, 0, k);
return ans;
}
};
三、自底向上寻找祖先
剑指 Offer 68 - II. 二叉树的最近公共祖先（简单难度）
236. 二叉树的最近公共祖先（中等难度）
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//如果当前节点为空，直接返回空
if(root==NULL) return NULL;
//如果当前节点值和p或者q中的一个相等，则返回当前节点
if(p->val==root->val||q->val==root->val)return root;
//递归调用
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
//如果左子树和右子树分别存在p和q
if (left != NULL && right != NULL)return root;
//如果右子树存在p和q
if (left == NULL && right != NULL)return right;
//如果左子树存在p和q
if (left != NULL && right == NULL) return left;
return NULL;
}
};
四、层序遍历
662. 二叉树最大宽度（中等难度）
class Solution {
public:
/*空节点下还可以挂载空节点,无法通过常规的层序遍历来为空节点保留子节点
给每个节点添加一个编号，通过编号来记录每层的宽度，但是这个编号可能会非常大
由于官方更新了测试用例，导致用原本二叉树的val记录编号（int型）会造成溢出。*/
int widthOfBinaryTree(TreeNode* root) {
int res=0;
queue<pair<TreeNode *, long long>> que; //队列记录二叉树的结点和一个对应的long long型编号
if(root==nullptr) return res;
que.push(make_pair(root, 0)); //根节点入队，并记录对应编号
while(!que.empty()){
int size=que.size();
int start = 0, end = 0;
// 从左到右遍历每一行
for(int i=0;i<size;++i){
// 出队
TreeNode* curNode = que.front().first;
long long curId = que.front().second;
que.pop();
// 记录当前行第一个和最后一个节点的编号
if (i == 0) start = curId;
if (i == size - 1) end = curId;
curId -= start; //缩小编号索引，以每层第一个结点的值为偏移值，保持每层结点之间的相对关系，缩小索引
// 入队
if(curNode->left){
que.push(make_pair(curNode->left, curId*2));
}
if(curNode->right){
que.push(make_pair(curNode->right, curId*2+1));
}
}
res=max(res, (int)(end-start+1));
}
return res;
}
};
958. 二叉树的完全性检验（中等难度）
给定一个二叉树的 root ，确定它是否是一个 完全二叉树 。
class Solution {
public:
bool isCompleteTree(TreeNode* root) {
queue<TreeNode*> que;
que.push(root);
bool end=false;// 是否遍历完所有的非空节点
while(!que.empty()){
int size=que.size();
// 从左到右遍历每一行
for(int i=0;i<size;++i){
// 出队
TreeNode* curNode = que.front();
que.pop();
// 第一次遇到null时end变成true，如果之后的所有节点都是 null，则说明是完全二叉树
if(curNode==nullptr) end = true;// 第一次遇到 null 时 end 变成 true
else{
// end 为 true 时遇到非空节点说明不是完全二叉树
if (end) return false;
// 入队
que.push(curNode->left);
que.push(curNode->right);
}
}
}
return true;
}
};