欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树找最近祖先节点和到某一节点的路径

程序员文章站 2022-07-09 12:39:10
...
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct TreeNode{
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int val) : val(val), left(nullptr), right(nullptr){}
};
//TreeNode* newNode(int val){
//	TreeNode* tmp = new TreeNode;
//	tmp->val = val;
//	tmp->left = nullptr;
//	tmp->right = nullptr;
//	return tmp;
//}
TreeNode* CreateTree(){
	TreeNode* p = nullptr;
	int val;
	cin >> val;
	if (val == 0)
		p = nullptr;
	else{
		p = new TreeNode(val);        //正确的使用方式  应该注意释放空间  delete和new对应存在
		p->left = CreateTree();
		p->right = CreateTree();
	}
	return p;
}
void PreOreder(TreeNode* root){
	if (root == nullptr)
		return;
	cout << root->val << ", ";
	PreOreder(root->left);
	PreOreder(root->right);
}
TreeNode* searchNode(TreeNode* root, int val){
	//临界条件
	if (root == nullptr)
		return nullptr;
	// 终止条件
	if (root->val == val){
		cout << "found" << endl;
		return root;
	}
	/*if (root->val != val && !root->left && !root->right)
		return nullptr;*/
	TreeNode*tmp_left = nullptr;
	TreeNode*tmp_right = nullptr;
	//框架  左子树 右子树
	if (root->left){
		tmp_left = searchNode(root->left, val);
	}
	if (root->right){
		tmp_right = searchNode(root->right, val);
	}
	//左右子树返回条件判断
	if (!tmp_left && !tmp_right) return nullptr;
	else if (!tmp_left || !tmp_right) return (!tmp_left) ? tmp_right : tmp_left;
}
/* root 根节点  val 查找的值 
	返回值:vector<vector<int> > ans
*/
void findPathToNode(TreeNode* root, int val, vector<int> &tmp, vector<vector<int> > &ans)
{
	/*犯错 :刚开始使用的是vector<vector<int> > ans作为返回值,自己在函数内申请了ans,
	但是返回之后,里面没有任何的数据。这也是经常犯的错误,所以改成引用,直接传递到函数中去
	*/
	if (root == nullptr) return ;
	tmp.push_back(root->val);         //注意push的位置在 终止条件之前
	if (root->val == val){
		ans.push_back(tmp);
		//tmp.clear();       //当时还在这里犹豫 是不是要清空,实际上是不需要的 
	}
	//常用的框架
	if (root->left) findPathToNode(root->left, val, tmp, ans);
	if (root->right) findPathToNode(root->right, val, tmp, ans);
	tmp.pop_back();
}
/* 输入  vector<vector<int> > ans
	输出 祖先节点
*/
int findNearestNeighbor(vector<vector<int> > ans){
	//仅限于2条路径
	const unsigned int size = ans.size();
	 
	vector<int> v1 = ans.front(); 
	vector<int> v2 = ans.back();
	const unsigned int s1= v1.size();
	const unsigned int s2= v1.size();
	for (int i = 0; i < min(s1, s2); i++){
		int j = i + 1;
		if (v1[j] != v2[j]) return v1[i];
	}
	return -1;
	
}
int main()
{	
	/*使用的输入数据 7 3 2 0 0 5 0 0 10 0 11  5 0 0 0
						7
					3       10
				2       5       11
							  5
	*/

	vector<vector<int> > ans;
	vector<int> tmp;
	
	TreeNode* root;
	root = CreateTree();
	cout << "pre_order start###" << endl;
	PreOreder(root);
	cout << "pre_order end###" << endl;
	TreeNode* target = searchNode(root, 5);
	if (target){
		cout << "target->val " << target->val << endl;
	}
	else cout << "Sorry ,not found! " << endl;
	findPathToNode(root, 5, tmp, ans);
	cout << "result " << ans.size() << endl;
	for (auto item : ans){
		for (auto a : item){
			cout << a << "\t";
		}
		cout << endl;
	}
	cout << "find nearest neighbor" << endl;
	int num = findNearestNeighbor(ans);
	cout << num << endl;
	system("pause");
	return 0;
}

上一篇: 背包公钥系统

下一篇: UML详解