数据结构上机复习三

1.寻找父节点

#include <iostream>
using namespace std;
struct TreeNode
{
	int val;
	TreeNode* left, * right;
};
TreeNode* CreateTree()
{
	int k;
	cin >> k;
	if (k == 0) return NULL;
	TreeNode* root = new TreeNode;
	root->val = k;
	root->left = CreateTree();
	root->right = CreateTree();
	return root;
}
TreeNode* fa(TreeNode* root,int k)
{
	if (root == NULL) return NULL;
	if (root->val == k) return NULL;
	if (((root->left)&&(root->left->val == k)) || ((root->right)&&(root->right->val == k))) return root;
	TreeNode* f1 = fa(root->left, k);
	if (f1) return f1;
	else return fa(root->right, k);
}
int main()
{
	TreeNode* root = CreateTree();
	int m;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int x;
		cin >> x;
		TreeNode* t = fa(root, x);
		if (t == NULL) cout << 0 << endl;
		else cout << t->val << endl;
	}
}

2.删除子树

#include <iostream>
using namespace std;
struct TreeNode
{
	int val;
	TreeNode* left, * right;
};
TreeNode* CreateTree()
{
	int k;
	cin >> k;
	if (k == 0) return NULL;
	TreeNode* root = new TreeNode;
	root->val = k;
	root->left = CreateTree();
	root->right = CreateTree();
	return root;
}
void Del(TreeNode* p)
{
	if (p == NULL) return;
	Del(p->left);
	Del(p->right);
	delete p;
}
TreeNode* Father(TreeNode* root, int x)
{
	if (root == NULL) return NULL;
	if (root->val == x) return NULL;
	if (((root->left) && (root->left->val == x)) || ((root->right) && (root->right->val == x)))
		return root;
	TreeNode* f1 = Father(root->left, x);
	TreeNode* f2 = Father(root->right, x);
	return (f1 != NULL) ? f1 : f2;
}
void TreeDel(TreeNode* root, int k,int& sign)
{
	if (root == NULL) return;
	if (root->val == k)
	{
		Del(root);
		return;
	}
	TreeNode* fa = Father(root, k);
	if (!fa)
	{
		sign = 1;
		return;
	}
	if (fa->left && fa->left->val == k)
	{
		Del(fa->left);
		fa->left = NULL;
	}
	else if (fa->right && fa->right->val == k)
	{
		Del(fa->right);
		fa->right = NULL;
	}
}
void InOrder(TreeNode* root)
{
	if (root == NULL) return;
	InOrder(root->left);
	cout << root->val << " ";
	InOrder(root->right);
}
int main()
{
	TreeNode* root = CreateTree();
	int m;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		int k;
		cin >> k;
		int sign = 0;
		TreeDel(root, k, sign);
		if (sign == 1)
			cout << 0;
		else
			InOrder(root);
		cout << endl;
	}
}

3.基于前、中序||后、中序构造

TreeNode* Create(string post, string in)
{
	int n = post.size();
	int m = in.size();
	if (m != n)
		return NULL;
	if (n < 1) return NULL;
	char rootval = post[n - 1];
	int k=-1;
	for (int i = 0; i < n; i++)
	{
		if (in[i] == rootval)
		{
			k = i;
			break;
		}
			
	}
	if (k == -1) return NULL;
	//左闭右开
	string l_post(post.begin(), post.begin() + k);
	string l_in(in.begin(), in.begin() + k);
	string r_post(post.begin() + k, post.end()-1);
	string r_in(in.begin() + k + 1, in.end());

	TreeNode* root = new TreeNode;
	root->val = rootval;
	root->left = Create(l_post, l_in);
	root->right = Create(r_post, r_in);
	return root;
}

4.最长路径

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode
{
	int val;
	TreeNode* left, * right;
};
TreeNode* CreateTree()
{
	int k;
	cin >> k;
	if (k == 0) return NULL;
	TreeNode* root = new TreeNode;
	root->val = k;
	root->left = CreateTree();
	root->right = CreateTree();
	return root;
}
int maxsum;
vector<int>maxpath;
void Traversal(TreeNode* root,vector<int>path, int sum)
{
	if (root == NULL) return;
	path.push_back(root->val);
	sum += root->val;
	if (root->left == NULL && root->right == NULL)
	{
		if (sum > maxsum)
		{
			maxsum = sum;
			maxpath = path;
		}
	}
	Traversal(root->left, path, sum);
	Traversal(root->right, path, sum);
}
int main()
{
	TreeNode* root = CreateTree();
	vector<int>path;
	Traversal(root, path, 0);
	cout << maxsum << endl;
	int n = maxpath.size();
	for (int i = 0; i < n; i++)
		cout << maxpath[i] << " ";
}

5.和等于某值路径

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode
{
	int val;
	TreeNode* left, * right;
};
TreeNode* CreateTree()
{
	int k;
	cin >> k;
	if (k == 0) return NULL;
	TreeNode* root = new TreeNode;
	root->val = k;
	root->left = CreateTree();
	root->right = CreateTree();
	return root;
}
vector<vector<int>>ans;
int k;
void Traversal(TreeNode* root, vector<int>path, int sum)
{
	if (root == NULL) return;
	path.push_back(root->val);//中
	sum += root->val;
	if (!root->left && !root->right && sum == k)
	{
		ans.push_back(path);
	}
	Traversal(root->left, path, sum);
	Traversal(root->right, path, sum);
}
int main()
{
	TreeNode* root = CreateTree();
	cin >> k;
	vector<int>path;
	Traversal(root, path, 0);
	int n = ans.size();
	cout << n << endl;
	for (int i = 0; i < n; i++)
	{
		int m = ans[i].size();
		for (int j = 0; j < m; j++)
			cout << ans[i][j] << " ";
		cout << endl;
	}
}

6.ab间路径（公共祖先）

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode
{
	int val;
	TreeNode* left, * right;
};
TreeNode* CreateTree()
{
	int k;
	cin >> k;
	if (k == 0) return NULL;
	TreeNode* root = new TreeNode;
	root->val = k;
	root->left = CreateTree();
	root->right = CreateTree();
	return root;
}

void traversal(TreeNode* root, vector<int>path,int x,vector<int>&path1)//查询由根结点到x的路径
{
	if (root == NULL) return;
	path.push_back(root->val);
	if (root->val == x)
	{
		path1 = path;
	}
	traversal(root->left, path, x,path1);
	traversal(root->right, path, x,path1);
}

int main()
{
	TreeNode* root = new TreeNode;
	root = CreateTree();
	int T;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		int a, b;
		cin >> a >> b;
		vector<int>path;
		vector<int>path1, path2;
		traversal(root, path, a,path1);
		traversal(root, path, b,path2);
		int n = min(path1.size(), path2.size());
		int j = 0;
		for (j = 0; j < n; j++)
		{
			if (path1[j] != path2[j])
				break;
		}
		j--;
		int len1 = path1.size() - 1;
		int len2 = path2.size() - 1;
		int len = len1 + len2 - 2 * j;
		cout << len << endl;
		for (int t = len1; t >= j; t--)
			cout << path1[t] << " ";
		for (int t = j + 1; t <= len2; t++)
			cout << path2[t] << " ";
		cout << endl;
	}
}

7.路径和2

#include <iostream>
#include <vector>
using namespace std;
struct TreeNode
{
	int val;
	TreeNode* left, * right;
};
TreeNode* CreateTree()
{
	int k;
	cin >> k;
	if (k == 0) return NULL;
	TreeNode* root = new TreeNode;
	root->val = k;
	root->left = CreateTree();
	root->right = CreateTree();
	return root;
}

int maxsum = 0;
vector<int>maxpath;
int minlen = 0x3f3f3f3f;
void traversal(TreeNode* root, vector<int>path, int fn, int len)
{
	if (root == NULL) return;
	//中
	if (fn > 0)
	{
		fn = fn + root->val;
		len++;
		path.push_back(root->val);
		if (fn > maxsum || (fn == maxsum && len < minlen))
		{
			maxsum = fn;
			maxpath = path;
			minlen = len;
		}
	}
	else
	{
		fn = root->val;
		len = 1;
		while (!path.empty())
			path.pop_back();
		path.push_back(root->val);
		if (fn > maxsum || (fn == maxsum && len < minlen))
		{
			maxsum = fn;
			maxpath = path;
			minlen = len;
		}
	}

	traversal(root->left, path, fn,len);
	traversal(root->right, path, fn,len);
		
	
}

int main()
{
	TreeNode* root = new TreeNode;
	root = CreateTree();
	vector<int>path;
	traversal(root, path, 0);
	cout << maxsum << endl;
	int n = maxpath.size();
	for (int i = 0; i < n; i++)
		cout << maxpath[i] << " ";
}