每日一题之二叉树
已知结点元素值为正整数且值不相同的一棵二叉树。
该二叉树通过给出其先序遍历序列和中序遍历序列构造而成。
输入一个整数x，针对此二叉树编写程序求出x的右子树中所有结点值的和（若x不在树上，输出-1）。
输入说明：第一行输入某二叉树的先序遍历序列 第二行输入该二叉树的中序遍历序列 第三行输入正整数x
输出说明：若x在树上，输出其右子树所有结点值的和（如果右子树为空，输出0）；如果x不在树上则输出-1。
输入样例：20 15 10 12 18 16 17 25 10 12 15 16 17 18 20 2515
输出样例：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; // 若节点为空，返回-1if (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];// 输入目标值xcout << "请输入目标值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;
}
根据先序和中序求二叉树的方式是先找根节点，两种遍历方式得到的序列同时开始查找，先序遍历的第一个数是根节点，然后再中序遍历中找到根节点，其左边的数就是左子树，右边的数就是右子树，以此类推，在两种遍历方式找到子树，再递推到整棵树。样例输出的数如下图所示：
