王道第五章–树与二叉树
一、题目导航
- 传送门——求二叉树的高度
- 传送门——重建二叉树
- 传送门——二叉树的镜像
- 传送门——二叉搜索树的第k个结点
- 传送门——二叉树中和为某一值的路径
- 传送门——树中两个结点的最低公共祖先
- 传送门——求二叉树结点最多的那一层结点个数/二叉树的最大宽度(bfs和dfs版本)
- 传送门——判别是否是完全二叉树
- 传送门——判断两棵二叉树是否相同
- 传送门——二叉树的层序遍历
- 传送门——二叉树的带权路径长度WPL
- 传送门——表达式树
补充:没有编程平台的题目
- 打印值为x的结点的所有祖先
- 删除以值为x的结点为根的子树,并释放相应空间
- 计算二叉树所有双分支结点的个数
- 已知满二叉树+前序序列,求后序序列
- 将二叉树的叶结点按从左到右的顺序连成一个单链表,叶结点右指针域存放单链表指针
二、题目答案
1. 求二叉树的高度
方法2: 二刷直接返回左右子树的最大高度
过程:从树的根节点的左右孩子 出发一直往下递归,直到递归到空结点,然后返回的时候,空结点那一层深度为max(0, 0) + 1 = 1,直到返回到根节点的左右孩子结束
/**
* 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 treeDepth(TreeNode* root) {
if (!root) return 0;
return max(treeDepth(root->left), treeDepth(root->right)) + 1;
}
};
方法1:dfs维护max_depth
/**
* 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 max_depth = 0;
void dfs(TreeNode* root, int depth)
{
if (!root) return;
max_depth = max(max_depth, depth);
if (root->left) dfs(root->left, depth + 1);
if (root->right) dfs(root->right, depth + 1);
}
int treeDepth(TreeNode* root) {
if (!root) return 0;
int depth = 1;
dfs(root, depth);
return max_depth;
}
};
2. 重建二叉树
/**
* 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> pre, in;
unordered_map<int, int> pos;
TreeNode* build(int il, int ir, int pl, int pr)
{
TreeNode* root = new TreeNode(pre[pl]);
int k = pos[pre[pl]];
if (il < k) root->left = build(il, k - 1, pl + 1, pl + 1 + k - 1 - il);
if (k < ir) root->right = build(k + 1, ir, pl + 1 + k - 1 - il + 1, pr);
return root;
}
TreeNode* buildTree(vector<int>& _pre, vector<int>& _in)
{
pre = _pre, in = _in;
if (pre.empty() || in.empty()) return NULL;
int il = 0, ir = in.size() - 1;
int pl = 0, pr = pre.size() - 1;
for (int i = 0; i <= ir; i ++) pos[in[i]] = i;
auto root = build(il, ir, pl, pr);
return root;
}
};
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:
void mirror(TreeNode* root) {
if (!root) return;
if (root->left) mirror(root->left);
if (root->right) mirror(root->right);
swap(root->left, root->right);
}
};
4. 二叉搜索树的第k个结点
/**
* 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> in;
void dfs(TreeNode* root)
{
if (!root) return;
if (root->left) dfs(root->left);
in.push_back(root->val);
if (root->right) dfs(root->right);
}
TreeNode* kthNode(TreeNode* root, int k)
{
dfs(root);
auto res = new TreeNode(in[k - 1]);
return res;
}
};
5. 二叉树中和为某一值的路径
/**
* 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<vector<int>> paths;
vector<int> nodes;
int sum;
void dfs(TreeNode* root)
{
if (!root) return;
nodes.push_back(root->val);
if (!root->left && !root->right) paths.push_back(nodes);
if (root->left) dfs(root->left);
if (root->right) dfs(root->right);
nodes.pop_back();
}
vector<vector<int>> findPath(TreeNode* root, int _sum) {
sum = _sum;
if (!root) return paths;
dfs(root);
vector<vector<int>> ans;
for (auto p : paths)
{
int res = 0;
for (int i = 0; i < p.size(); i ++) res += p[i];
if (res == sum) ans.push_back(p);
}
return ans;
}
};
6. 树中两个结点的最低公共祖先
/**
* 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) return NULL;
if (root == p || root == q) return root;
// 1. 若p、q在左子树上,left则是p、q在左子树上的最近祖先
// 2. 若p、q在右子树上,right则是p、q在右子树上的最近祖先
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
// (1).左、右子树均不为空,则表示p和q一个在左子树另一个在右子树,他们的根结点就是最近祖先
if (left && right) return root;
// (2). 左子树不为空,则表示p和q都在左子树上
// (3). 右子树不为空,则表示p和q都在右子树上
if (left) return left;
else return right;
}
};
7. 求二叉树结点最多的那一层结点个数
(1) BFS版本
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* 求这可树的最大宽度
* @param head TreeNode类 树的根节点
* @return int整型
*/
queue<TreeNode*> q;
int cnt[100010];
int depth = 0, max_width = 0;
int getMaxWidth(TreeNode* root) {
// write code here
if (!root) return max_width;
q.push(root);
while (q.size())
{
queue<TreeNode*> tmp;
cnt[depth ++] = q.size();
while (q.size())
{
auto t = q.front();
q.pop();
if (t->left) tmp.push(t->left);
if (t->right) tmp.push(t->right);
}
q = tmp;
}
for (int i = 0; i <= depth; i ++)
if (cnt[i] > max_width) max_width = cnt[i];
return max_width;
}
};
(2) DFS版本
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
* 求这可树的最大宽度
* @param head TreeNode类 树的根节点
* @return int整型
*/
int cnt[100010];
int depth = 0, max_depth = 0;
int max_width = 0;
void dfs(TreeNode* root, int depth)
{
cnt[depth] ++;
max_depth = max(max_depth, depth);
if (root->left) dfs(root->left, depth + 1);
if (root->right) dfs(root->right, depth + 1);
}
int getMaxWidth(TreeNode* root) {
// write code here
if (!root) return max_width;
dfs(root, depth);
for (int i = 0; i <= max_depth; i ++)
if (cnt[i] > max_width) max_width = cnt[i];
return max_width;
}
};
8. 判断是不是完全二叉树
(1) 多个x结点,找其祖先萌
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return bool布尔型
*/
// 关键点:层序遍历,把空结点也放队列,如果空结点之后还有非空结点,则说明,不是完全二叉树
queue<TreeNode*> q;
bool nullstr = false; // nullstr用于给空结点做标记
bool isCompleteTree(TreeNode* root) {
if (!root) return true;
q.push(root);
while (q.size())
{
auto t = q.front();
q.pop();
if (t == NULL) nullstr = true;
else
{
if (nullstr) return false;
// 左右孩子均入队,不管是否为空
q.push(t->left);
q.push(t->right);
}
}
return true;
}
};
(2) 一个x结点,找其祖先萌
vector<int> nodes;
void dfs(TreeNode* root, int x)
{
if (!root) return;
if (root->val == x) return;
nodes.push_back(root->val);
if (root->left) dfs(root->left, x);
if (root->right) dfs(root->right, x);
nodes.pop_back();
}
vector<int> GrandParent(TreeNode* root, int x)
{
dfs(root, x);
return nodes;
}
9. 判断两棵二叉树是否相同
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true;
else if (!p && q) return false;
else if (p && !q) return false;
else
{
if (p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
}
};
10. 二叉树的层序遍历(本题是将二叉树一层层的序列输出)
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > levelOrder(TreeNode* root) {
// write code here
vector<vector<int>> paths;
if (!root) return paths;
queue<TreeNode*> q;
q.push(root);
while (q.size())
{
queue<TreeNode*> tmp;
vector<int> nodes;
while (q.size())
{
auto t = q.front();
q.pop();
nodes.push_back(t->val);
if (t->left) tmp.push(t->left);
if (t->right) tmp.push(t->right);
}
q = tmp;
paths.push_back(nodes);
}
return paths;
}
};
11. 二叉树的带权路径长度
复习时最新版:将WPL问题转化成找路径的问题
/**
* 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<vector<int>> paths;
vector<int> nodes;
void dfs(TreeNode* root)
{
if (!root) return;
nodes.push_back(root->val);
if (!root->left && !root->right) paths.push_back(nodes);
if (root->left) dfs(root->left);
if (root->right) dfs(root->right);
nodes.pop_back();
}
int pathSum(TreeNode* root) {
if (!root) return 0;
dfs(root);
int WPL = 0;
for (auto p : paths)
{
int len = p.size();
WPL += p[len - 1] * (len - 1);
}
return WPL;
}
};
通用方法:通过找每个结点的深度,每当遍历到叶子结点的时候 就用其 深度*根结点的值 来算一下其路径长度
/**
* 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 WPL;
void dfs(TreeNode* root, int depth)
{
if (!root) return;
// 如果是叶子结点,那就算一下路径长度
if (!root->left && !root->right) WPL += root->val * depth;
if (root->left) dfs(root->left, depth + 1);
if (root->right) dfs(root->right, depth + 1);
}
int pathSum(TreeNode* root) {
if (!root) return 0;
int depth = 0;
dfs(root, depth);
return WPL;
}
};
12. 表达式树
/**
* Definition for a binary tree node.
* struct TreeNode {
* string val;
* TreeNode *left;
* TreeNode *right;
* };
*/
class Solution {
public:
string res;
void dfs(TreeNode* root)
{
if (!root) return;
// 叶子结点遍历完不需要加括号,非叶子结点遍历完需要加括号
if (!root->left && !root->right) res += root->val; // 叶子结点需注意!
else
{
// 非叶子结点:'(' + 左子树 + 根 + 右子树 + ')'
res += '(';
if (root->left) dfs(root->left);
res += root->val;
if (root->right) dfs(root->right);
res += ')';
}
}
string expressionTree(TreeNode* root) {
dfs(root);
return res.substr(1, res.size() - 2);
}
};
补充:没有编程平台的题目
1. 打印值为x的结点的所有祖先
/**
* 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<vector<int>> paths;
vector<int> nodes;
void dfs(TreeNode* root, int x)
{
if (!root) return;
if (root->val == x) paths.push_back(nodes);
nodes.push_back(root->val);
if (root->left) dfs(root->left, x);
if (root->right) dfs(root->right, x);
nodes.pop_back();
}
vector<vector<int>> findPath(TreeNode* root, int x) {
dfs(root, x);
return paths;
}
};
2. 删除以值为x的结点为根的子树,并释放相应空间
void DeleteXTree(TreeNode* root)
{
// 类似后序遍历,即先删除左右子树再删除根
if (!root) return;
DeleteXTree(root->left);
DeleteXTree(root->right);
free(root);
}
void bfs(TreeNode* root, int x)
{
if (root->val == x)
{
DeleteXTree(root);
return;
}
queue<TreeNode*> q;
q.push(root);
while (q.size())
{
auto t = q.front();
q.pop();
if (t->left)
{
if (t->left->val == x)
{
DeleteXTree(t->left);
t->left = NULL;
}
else q.push(t->left);
}
if (t->right)
{
if (t->right->val == x)
{
DeleteXTree(t->right);
t->right = NULL;
}
else q.push(t->right);
}
}
}
3. 计算二叉树所有双分支结点的个数
int cnt = 0;
void dfs(TreeNode* root)
{
if (!root) return;
if (root->left && root->right) cnt ++;
if (root->left) dfs(root->left);
if (root->right) dfs(root->right);
}
int Number(TreeNode* root)
{
dfs(root);
return cnt;
}
4. 已知满二叉树+前序序列,求后序序列
void PreToPost(ElemType pre[], int l1, int h1, ElemType post[], int l2, int h2)
{
if (l1 <= h1)
{
post[h2] = pre[l1];
int half = (h1 - l1) / 2;
PreToPost(pre, l1 + 1, l1 + half, post, l2, l2 + half - 1);
PreToPost(pre, l1 + half + 1, h1, post, l2 + half, h2 - 1);
}
}
5. 将二叉树的叶结点按从左到右的顺序连成一个单链表,叶结点右指针域存放单链表指针
// 设计一个算法将二叉树的叶结点按从左到右的顺序连成一个单链表,表头指针为head,
// 二叉树按二叉链表方式存储,链接时用叶结点的右指针域来存放单链表指针
// 找叶子结点,尾插法
ListNode* head = new ListNode(-1);
ListNode* pre = head;
void insert(TreeNode* root)
{
root->right = NULL;
pre->next = root;
pre = root;
}
void dfs(TreeNode* root)
{
if (!root) return;
if (!root->left && !root->right) insert(root);
if (root->left) dfs(root->left);
if (root->right) dfs(root->right);
}
ListNode* BtoLink(TreeNode* root)
{
dfs(root);
return head;
}