保研机试备考六:树的遍历
AcWing 3766. 二叉树的带权路径长度
题目
https://www.acwing.com/problem/content/3769/
思路
二叉树的带权路径长度(WPL)是二叉树中所有叶结点的带权路径长度之和,也就是每个叶结点的深度与权值之积的总和。
给定一棵二叉树 T,请你计算并输出它的 WPL。
这题涉及到了层数,对于树的遍历应该使用层次遍历。
使用一个队列来辅助。
详细思路见代码
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
typedef pair<TreeNode*,int> PII; //队列中的元素是树节点指针和层数的pair对
class Solution {
public:
int pathSum(TreeNode* root) {
queue<PII> q;
int sum=0; //总和
q.push({root,0}); //把根节点放进去,层数为0
while(!q.empty())
{
auto t=q.front();
q.pop();
if(t.first->left==NULL&&t.first->right==NULL) //如果是叶结点
sum+=t.first->val*t.second; //算带权路径值,加到总和上
//把儿子节点(若存在),入队,层数+1
if(t.first->left!=NULL)
q.push({t.first->left,t.second+1});
if(t.first->right!=NULL)
q.push({t.first->right,t.second+1});
}
return sum;
}
};
AcWing 18. 重建二叉树
题目
https://www.acwing.com/problem/content/23/
思路
前序(根)遍历顺序:根→左→右
中序(根)遍历顺序:左→根→右
后序(根)遍历顺序:左→右→根
怎么记忆?
不管是前序、中序还是后序,这个前、中、后都是根的顺序,左儿子永远在右儿子前被访问。
递归建立整棵二叉树:先递归创建左右子树,然后创建根节点,并让指针指向两棵子树。
具体步骤如下:
- 1:先利用前序遍历找根节点:前序遍历的第一个数,就是根节点的值;
- 2:在中序遍历中找到根节点的位置 k,则 k左边是左子树的中序遍历,右边是右子树的中序遍历;
- 3:假设左子树的中序遍历的长度是 l,则在前序遍历中,根节点后面的 l 个数,是左子树的前序遍历,剩下的数是右子树的前序遍历;
- 4:有了左右子树的前序遍历和中序遍历,我们可以先递归创建出左右子树,然后再创建根节点;
代码
/**
* 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> preorder,inorder; //作为全局变量用,减少传参
unordered_map<int,int> pos; //哈希表,用来快速查找根节点在中序遍历数组中的位置
TreeNode* build(int a,int b,int x,int y) //递归重建
{
if(a>b) return NULL; //长度<0,则为空了
int t=pos[preorder[a]]; //找到根节点在中序遍历中的位置
auto root=new TreeNode(preorder[a]); //创建根节点
root->left=build(a+1,a+1+t-x-1,x,t-1); //递归到左子树
root->right=build(a+1+t-x,b,t+1,y); //递归到右子树
return root;
}
TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
preorder=_preorder,inorder=_inorder;
int n=inorder.size();
for(int i=0;i<n;i++) pos[inorder[i]]=i; //构建节点值和数组下标的哈希表
return build(0,n-1,0,n-1);
}
};