已知结点元素值为正整数且值不相同的一棵二叉树。
该二叉树通过给出其先序遍历序列和中序遍历序列构造而成。
输入一个整数x,针对此二叉树编写程序求出x的右子树中所有结点值的和(若x不在树上,输出-1)。
输入说明:第一行输入某二叉树的先序遍历序列 第二行输入该二叉树的中序遍历序列 第三行输入正整数x
输出说明:若x在树上,输出其右子树所有结点值的和(如果右子树为空,输出0);如果x不在树上则输出-1。
输入样例:20 15 10 12 18 16 17 25
10 12 15 16 17 18 20 25
15
输出样例:51
在解决这道题之前,我们先来了解一个树的四种遍历方式:先序遍历、中序遍历、后序遍历、层序遍历。
#include<iostream>
#include<queue>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x):val(x),left(nullptr),right(nullptr){
}
};
void PreOrder(TreeNode* root); //前序遍历
void InOrder(TreeNode* root); //中序遍历
void PostOrder(TreeNode* root); //后序遍历
void LevelOrder(TreeNode* root); //层序遍历
int main(){
TreeNode* root=new TreeNode(1);
root->left=new TreeNode(2);
root->right=new TreeNode(3);
root->left->left=new TreeNode(4);
root->left->right=new TreeNode(4);
root->right->left=new TreeNode(5);
PreOrder(root);
cout<<endl;
InOrder(root);
cout<<endl;
PostOrder(root);
cout<<endl;
LevelOrder(root);
cout<<endl;
return 0;
}
void PreOrder(TreeNode* root){
if(!root){
return ;
}
cout<<root->val<<" ";
PreOrder(root->left);
PreOrder(root->right);
}
void InOrder(TreeNode* root){
if(!root){
return;
}
InOrder(root->left);
cout<<root->val<<" ";
InOrder(root->right);
}
void PostOrder(TreeNode* root){
if(!root){
return ;
}
PostOrder(root->left);
PostOrder(root->right);
cout<<root->val<<" ";
}
void LevelOrder(TreeNode* root){
if(!root){
return;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* cur=q.front();
q.pop();
cout<<cur->val<<" ";
if(cur->left){
q.push(cur->left);
}
if(cur->right){
q.push(cur->right);
}
}
//cout<<endl;
}
前序遍历、中序遍历和后序遍历的思路都差不多,只不过要区分三种方式,其实前、中、后主要是指根节点的遍历顺序。
前序遍历(先序遍历)是指根结点先遍历,再依次遍历它的左右结点。
中序遍历是先遍历左子树结点,再遍历根节点,然后遍历右子树。
后序遍历是指先遍历完左右子树结点,再遍历根结点。
而层序遍历则需要借助队列辅助,简单来说就是需要一层一层去遍历,如下图:
假设我们需要层序遍历这棵树,那么我们需要将根结点A先放入队列,然后再将当前结点指向A,将队列头结点出队,然后输出当前结点的值A,再遍历当前结点的左右子树结点,即B、C。将B、C入队,然后进入下一次循环,B为当前队列头结点,那么将B出队,同时遍历B的左右子树结点D、E,同时将D、E入队。那么此时队列的元素为C(头结点)、D、E。所以将C出队,遍历它的左右子树结点F,再将F入队。此时队列元素为D、E、F。遍历D、E、F,都未遍历到左右子树,且都将它们出队,此时队列为空,循环结束。
现在回到这个题,它给出了二叉树的先序和中序遍历,然后给出目标值,要我们求出这棵树中是否存在目标值,再求出目标值的右子树之和。
简单分析一下,解决这道题的思路就是先根据先序和中序遍历求出树的根节点,然后找出目标值,返回其右子树的和。
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 初始化节点
};
// 使用先序和中序遍历构建二叉树
TreeNode* buildTree(const vector<int>& preorder, int preStart, int preEnd,
const vector<int>& inorder, int inStart, int inEnd,
unordered_map<int, int>& inMap) {
if (preStart > preEnd || inStart > inEnd) return nullptr; // 若范围不合法,返回空节点
// 创建根节点,根节点值为先序遍历的第一个元素
TreeNode* root = new TreeNode(preorder[preStart]);
int inRoot = inMap[root->val]; // 查找根节点在中序遍历中的位置
int numsLeft = inRoot - inStart; // 计算左子树节点的数量
// 递归构建左子树
root->left = buildTree(preorder, preStart + 1, preStart + numsLeft,
inorder, inStart, inRoot - 1, inMap);
// 递归构建右子树
root->right = buildTree(preorder, preStart + numsLeft + 1, preEnd,
inorder, inRoot + 1, inEnd, inMap);
return root; // 返回根节点
}
// 计算某节点的右子树所有节点值的和
int sumRightSubtree(TreeNode* root) {
if (!root) return 0; // 若节点为空,返回0
// 递归计算左右子树的节点值之和并加上当前节点值
return root->val + sumRightSubtree(root->left) + sumRightSubtree(root->right);
}
// 在二叉树中查找值为x的节点,并返回其右子树的节点值和
int findAndSumRightSubtree(TreeNode* root, int x) {
if (!root) return -1; // 若节点为空,返回-1
if (root->val == x) return sumRightSubtree(root->right); // 找到目标节点,计算右子树节点值和
int leftSearch = findAndSumRightSubtree(root->left, x); // 在左子树中递归查找
if (leftSearch != -1) return leftSearch; // 如果在左子树中找到目标节点,直接返回结果
return findAndSumRightSubtree(root->right, x); // 否则在右子树中递归查找
}
int main() {
vector<int> preorder, inorder;
int x, n;
// 输入先序遍历序列长度
cout << "请输入先序遍历序列长度: ";
cin >> n;
// 输入先序遍历序列
cout << "请输入先序遍历序列: ";
preorder.resize(n);
for (int i = 0; i < n; i++) cin >> preorder[i];
// 输入中序遍历序列
cout << "请输入中序遍历序列: ";
inorder.resize(n);
for (int i = 0; i < n; i++) cin >> inorder[i];
// 输入目标值x
cout << "请输入目标值x: ";
cin >> x;
// 构建inorder索引哈希表,用于快速定位节点在中序遍历中的位置
unordered_map<int, int> inMap;
for (int i = 0; i < n; i++) inMap[inorder[i]] = i;
// 使用先序和中序遍历序列构建二叉树
TreeNode* root = buildTree(preorder, 0, n - 1, inorder, 0, n - 1, inMap);
// 查找值为x的节点的右子树节点值和,并输出结果
int result = findAndSumRightSubtree(root, x);
cout << result << endl;
return 0;
}
根据先序和中序求二叉树的方式是先找根节点,两种遍历方式得到的序列同时开始查找,先序遍历的第一个数是根节点,然后再中序遍历中找到根节点,其左边的数就是左子树,右边的数就是右子树,以此类推,在两种遍历方式找到子树,再递推到整棵树。样例输出的数如下图所示:
标签:结点,遍历,TreeNode,int,每日,二叉树,一题,root,节点 From: https://blog.csdn.net/m0_73096516/article/details/143649999