跳到主要内容剑指 Offer 第二版：二叉树算法解析 | 极客日志C++算法
剑指 Offer 第二版：二叉树算法解析
剑指 Offer 第二版中的二叉树相关算法题，包含路径和查找、序列化、搜索树转换、第 k 个节点、深度计算、平衡性判断及最近公共祖先。通过回溯、递归、层序遍历等策略提供 C++ 解决方案。
怪力乱神3 浏览 一、JZ34 二叉树中和为某一值的路径
回溯法本质是一个基于 DFS 的穷举的过程。
- 先添加值
- 在判定现有结果是否满足条件
- DFS
- 回退
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
vector<vector<int>> FindPath(TreeNode* root, int target) {
if(!root) return ret;
dfs(root, target);
return ret;
}
void dfs(TreeNode* root, int target){
path.emplace_back(root->val);
target -= root->val;
if(!root->left && !root->right && !target) ret.emplace_back(path);
else{
if(root->left) dfs(root->left, target);
if(root->right) dfs(root->right, target);
}
path.pop_back();
}
};
二、扩展 JZ34 二叉树中和为某一值的路径（任意路径）
既然要找所有路径上节点和等于目标值的路径个数，那我们肯定先找这样的路径起点。但是我们不知道起点究竟在哪里，而且任意节点都有可能是起点，那我们就前序遍历二叉树的所有节点，每个节点都可以作为一次起点，即子树的根节点。
查找路径的时候呢，也需要往下遍历，因此还可以继续前序遍历该子树，在遍历的过程遇到一个节点，sum 相应减少，sum==0，则找到一种情况。但是因为该题的值有正有负，所以不能直接退出，而是要接着去他的左子树和右子树看看！！
class Solution {
public:
int ret = 0;
void dfs(TreeNode* root, sum) {
(!root) ;
sum -= root->val;
(sum == ) ++ret;
(root->left, sum);
(root->right, sum);
}
{
(!root) ;
(root, sum);
(root->left, sum);
(root->right, sum);
ret;
}
};
微信扫一扫，关注极客日志
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
- Markdown转HTML
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
- HTML转Markdown
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
int
if
return
if
0
dfs
dfs
int FindPath(TreeNode* root, int sum)
if
return
0
dfs
FindPath
FindPath
return
三、JZ36 二叉搜索树与双向链表
class Solution {
public:
void Inorder(TreeNode* cur, TreeNode*& prev) {
if (!cur) return;
Inorder(cur->left, prev);
cur->left = prev;
if (prev) prev->right = cur;
prev = cur;
Inorder(cur->right, prev);
}
TreeNode* Convert(TreeNode* root) {
if (!root) return nullptr;
TreeNode* prev = nullptr;
Inorder(root, prev);
while (root->left) root = root->left;
return root;
}
};
四、JZ37 序列化二叉树 (重点)
根据重建二叉树，我们知道可以从前序遍历序列和中序遍历序列中构建一颗二叉树，受此启发，我们可以先把一个二叉树序列化成一个前序序列和中序序列，然后在反序列化时通过两个序列重构出原二叉树。但是这个思路有两个缺点：1、必须要求二叉树中不能有数值重复的点。2、只有当两个序列的所有数据都读出来了才能够进行反序列化，如果两个序列的数据是从一个流里读出来的（没有并行），那么这个过程会花费很多时间！
思路 1：实际上如果二叉树的序列化是从根开始的，那么反序列化在根节点的数值读出来的时候就可以开始了，因此我们可以使用前序遍历来序列化二叉树！！
#include <string>
class Solution {
public:
void SerializeHelper(TreeNode *root, string &s){
if(root == nullptr) {
s += '#';
return;
}
s += to_string(root->val) + ',';
SerializeHelper(root->left, s);
SerializeHelper(root->right, s);
}
char* Serialize(TreeNode *root) {
if(!root) return nullptr;
string s;
SerializeHelper(root, s);
char* ret = new char[s.size() + 1];
strcpy(ret, s.c_str());
ret[s.size()] = '\0';
return ret;
}
TreeNode* Deserialize(char *&str) {
if(str == nullptr || *str == '\0') return nullptr;
if(*str == '#') {
++str;
return nullptr;
}
int val = 0;
while(*str != ',' && *str != '\0'){
val = val * 10 + (*str - '0');
++str;
}
auto* root = new TreeNode(val);
++str;
root->left = Deserialize(str);
root->right = Deserialize(str);
return root;
}
};
我们使用 999 作为无效值（当然也可以不使用数字，使用某个特殊字符进行表示，只要能在反序列时有所区分即可），并建立占位节点 emptyNode 用来代指空节点（emptyNode.val = 999）
class Solution {
public:
TreeNode* emptynode = new TreeNode(999);
char* Serialize(TreeNode *root) {
if(!root) return nullptr;
queue<TreeNode*> q;
string s;
q.push(root);
while(!q.empty()){
TreeNode* t = q.front();
q.pop();
s += to_string(t->val) + ' ';
if(t != emptynode){
q.push(t->left ? t->left : emptynode);
q.push(t->right ? t->right : emptynode);
}
}
char* ret = new char[s.size() + 1];
strcpy(ret, s.c_str());
ret[s.size()] = '\0';
return ret;
}
TreeNode* Deserialize(char *str) {
if(str == nullptr) return nullptr;
stringstream is(str);
string s;
vector<int> v;
while(is >> s) v.emplace_back(stoi(s));
int n = v.size();
auto root = new TreeNode(v[0]);
queue<TreeNode*> q;
q.push(root);
for(int i = 1; i < n - 1; i += 2){
TreeNode* t = q.front();
q.pop();
if(v[i] != 999){
auto left = new TreeNode(v[i]);
t->left = left;
q.push(left);
}
if(v[i+1] != 999){
auto right = new TreeNode(v[i+1]);
t->right = right;
q.push(right);
}
}
return root;
}
};
要注意借助 stringstream 流来帮助我们切割字符串 如果是空格可以直接用流，如果是其他符号可以借助 getline
五、JZ54 二叉搜索树的第 k 个节点
思路 1：中序遍历时到达第 k 个元素 (二叉搜索树，不存在两个相同的节点值)
class Solution {
public:
int ret;
void dfs(TreeNode* root, int& k){
if(root == nullptr || k <= 0) return;
dfs(root->left, k);
if(--k == 0) { ret = root->val; return; }
dfs(root->right, k);
}
int KthNode(TreeNode* root, int k) {
if(root == nullptr || k == 0) return -1;
dfs(root, k);
return k <= 0 ? ret : -1;
}
};
思路 2：利用栈，采用循环中序遍历的方式 (参照非递归遍历二叉树)
class Solution {
public:
int KthNode(TreeNode* root, int k) {
if (!root || k <= 0) return -1;
stack<TreeNode*> st;
TreeNode* cur = root;
while (cur || !st.empty()) {
while (cur) {
st.push(cur);
cur = cur->left;
}
cur = st.top();
st.pop();
if (--k == 0) return cur->val;
cur = cur->right;
}
return -1;
}
};
六、JZ55 二叉搜索树的深度
class Solution {
public:
int TreeDepth(TreeNode* root) {
if(!root) return 0;
return 1 + max(TreeDepth(root->left), TreeDepth(root->right));
}
};
思路 2：用一个变量去统计深度 然后再用一个 max 去找最深
class Solution {
public:
void TreeDepthHelp(TreeNode* root, int cur, int& max){
if(!root){
if(max < cur) max = cur;
return;
}
TreeDepthHelp(root->left, cur + 1, max);
TreeDepthHelp(root->right, cur + 1, max);
}
int TreeDepth(TreeNode* root) {
if(!root) return 0;
int depth = 0, max = 0;
TreeDepthHelp(root, depth, max);
return max;
}
};
七、扩展 JZ55 判断该树是不是平衡二叉树 (后序遍历)
左右子树高度差不超过 1，且左右子树都是平衡二叉树
class Solution {
public:
int deep(TreeNode* root){
if(!root) return 0;
return 1 + max(deep(root->left), deep(root->right));
}
bool IsBalanced_Solution(TreeNode* root) {
if(!root) return true;
int left = deep(root->left);
int right = deep(root->right);
if(left - right < -1 || left - right > 1) return false;
return IsBalanced_Solution(root->left) && IsBalanced_Solution(root->right);
}
};
这个代码虽然简洁，但是一个节点需要判断多次，所以我们用后序遍历的方式遍历二叉树的每个节点，那么再遍历这个节点之前我们已经遍历了它的左右子树，因此只要在遍历的时候记录他的深度，就可以一边遍历一般判断是不是平衡的了！！
class Solution {
public:
bool IsBalanced(TreeNode* root, int &depth){
if(!root) return true;
int left = 0, right = 0;
if(IsBalanced(root->left, left) && IsBalanced(root->right, right)){
int diff = left - right;
if(diff <= 1 && diff >= -1){
depth = 1 + max(left, right);
return true;
}
}
return false;
}
bool IsBalanced_Solution(TreeNode* root) {
int depth = 0;
return IsBalanced(root, depth);
}
};
八、JZ68 二叉搜索树的最近公共祖先
二叉搜索树是排序过的，位于左子树的节点都比父节点小，而位于右子树的节点都比父节点大，我们只需要从树的根节点开始和两个输入的节点进行比较，如果当前节点的值比两个节点的值都大，那么最低的公共祖先一定在当前节点的左子树中，如果都比两个节点的值小，那么就一定在他的右子树中，如果一个大一个小，那就说明当前当前节点一定是结果！！
class Solution {
public:
int lowestCommonAncestor(TreeNode* root, int p, int q) {
while(root){
if(root->val > p && root->val > q) root = root->left;
else if(root->val < p && root->val < q) root = root->right;
else break;
}
return root->val;
}
};
九、扩展 JZ68 二叉树的最近公共祖先 (重点)
这样写的话是前序遍历，每次都要重复遍历很多点，复杂度太高了（如果遇到歪脖子树，那复杂都就是 N^2）
class Solution {
public:
bool isintree(TreeNode* root, int x){
if(!root) return false;
return root->val == x || isintree(root->left, x) || isintree(root->right, x);
}
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
if(root->val == o1 || root->val == o2) return root->val;
bool pleft = isintree(root->left, o1);
bool pright = !pleft;
bool qleft = isintree(root->left, o2);
bool qright = !qleft;
if(pleft && qright || qleft && pright) return root->val;
else if(pleft && qleft) return lowestCommonAncestor(root->left, o1, o2);
else return lowestCommonAncestor(root->right, o1, o2);
}
};
根据启发思路 2，如果我们有父节点 就可以转化成相交链表的问题，那么既然我们不能通过父节点回溯，那么就可以通过容器来将遍历过的节点存起来！！
class Solution {
public:
bool dfs(TreeNode* root, int x, stack<int>& path){
if(!root) return false;
path.push(root->val);
if(root->val == x || dfs(root->left, x, path) || dfs(root->right, x, path)) return true;
path.pop();
return false;
}
int lowestCommonAncestor(TreeNode* root, int p, int q) {
if(root->val == p || root->val == q) return root->val;
stack<int> pPath, qPath;
dfs(root, p, pPath);
dfs(root, q, qPath);
while(pPath.size() != qPath.size()){
if(pPath.size() > qPath.size()) pPath.pop();
else qPath.pop();
}
while(pPath.top() != qPath.top()){
pPath.pop();
qPath.pop();
}
return pPath.top();
}
};
思路 3：如果我们两个一起找，只要存在一个就返回对应的点（后序遍历）
class Solution {
public:
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
if(!root) return 0;
if(root->val == o1 || root->val == o2) return root->val;
int left = lowestCommonAncestor(root->left, o1, o2);
int right = lowestCommonAncestor(root->right, o1, o2);
if(!left) return right;
if(!right) return left;
return root->val;
}
};
时间复杂度是 O(n)，因为每个节点只会遍历一次
空间复杂度是 O(n)，最坏的情况退化到链表
