每日一题之二叉树

已知结点元素值为正整数且值不相同的一棵二叉树。
该二叉树通过给出其先序遍历序列和中序遍历序列构造而成。
输入一个整数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;
}

根据先序和中序求二叉树的方式是先找根节点，两种遍历方式得到的序列同时开始查找，先序遍历的第一个数是根节点，然后再中序遍历中找到根节点，其左边的数就是左子树，右边的数就是右子树，以此类推，在两种遍历方式找到子树，再递推到整棵树。样例输出的数如下图所示：