首页 > 其他分享 >每日一题之二叉树

每日一题之二叉树

时间:2024-11-10 20:19:42浏览次数:3  
标签:结点 遍历 TreeNode int 每日 二叉树 一题 root 节点

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

相关文章

  • 蓝桥杯每日真题 - 第7天
    题目:(爬山)题目描述(X届C&C++B组X题)解题思路:前缀和构造:为了高效地计算子数组的和,我们可以先构造前缀和数组a,其中a[i]表示从第1个元素到第i个元素的和。这样,对于任意区间[i,j]的子数组和,可以通过a[j]-a[i-1]快速得到。枚举所有区间和:用双重循环枚举所有可......
  • 根据二叉树创建字符串
    题目:606.根据二叉树创建字符串-力扣(LeetCode)给你二叉树的根节点 root ,请你采用前序遍历的方式,将二叉树转化为一个由括号和整数组成的字符串,返回构造出的字符串。空节点使用一对空括号对 "()" 表示,转化后需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空......
  • 代码随想录算法训练营第18天| 530.二叉搜索树的最小绝对差, 501.二叉搜索树中的众数 , 2
    530.二叉搜索树的最小绝对差文章链接:https://programmercarl.com/0530.二叉搜索树的最小绝对差.html视频链接:https://www.bilibili.com/video/BV1DD4y11779/?vd_source=6cb513d59bf1f73f86d4225e9803d47b题目链接:https://leetcode.cn/problems/minimum-absolute-difference-in......
  • 每日一题.设计相邻元素求和服务;暴力算法与哈希表的运用
    本题出自LeetCode每日一题3242,可以说比昨天的那道“每日抑题”简单不少呀,就是代码长一点,同时本题目使用了两种不同的方法,并对每一种用法进行了深度解析。本文全长5000字。题目 给你一个 nxn 的二维数组 grid,它包含范围 [0,n2-1] 内的不重复元素。实现 neighbo......
  • 判断该给定的二叉树是否为二叉搜索树
    习题4.3是否二叉搜索树/*typedefstructTNode*Position;typedefPositionBinTree;structTNode{ ElementTypeData; BinTreeLeft; BinTreeRight;};*/BinTreeB=NULL;//全局指针,用来记录中序的上一个结点boolIsBST(BinTreeT){ //如果结点为空直接返回tru......
  • sicp每日一题[2.73]
    最近状态不太好,再加上2.73前面的内容有点多,学的有点吃力,所以昨天就没做。。Exercise2.73Section2.3.2describedaprogramthatperformssymbolicdifferentiation:(define(derivexpvar)(cond((number?exp)0)((variable?exp)(if(same-va......
  • 力扣(LeetCode)106. 从中序与后序遍历序列构造二叉树
    一、目标  给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。二、代码分析总体代码:/***Definitionforabinarytreenode.*publicclassTreeNode{*int......
  • 104.力扣(leetcode)二叉树的最大深度(JAVA)
    一、目标给定一个二叉树 root ,返回其最大深度。二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。二、代码分析总代码:/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeN......
  • 257. 力扣(LeetCode)二叉树的所有路径(JAVA)
    一、目标给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。二、代码解读总代码:/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*......
  • 代码随想录算法训练营第十七天| 654.最大二叉树 , 617.合并二叉树 , 700.二叉搜索树中的
    654.最大二叉树文章链接:https://programmercarl.com/0654.最大二叉树.html题目链接:https://leetcode.cn/problems/maximum-binary-tree/description/classSolution{public:TreeNode*traversal(vector<int>&nums,intleft,intright){if(left>=right)ret......