leetcode上树的一些算法

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;

#define error(format, ...) printf(format, __VA_ARGS__)
struct TreeNode
{
	TreeNode *left;
	TreeNode *right;
	int val;
	// TreeNode(int v) : val(v),left(NULL),right(NULL){}
};

// 创建二叉树
TreeNode *createBinaryTree(TreeNode *Arr, int size)
{
	for (int i = 0; i <= size; i++)
	{
		(Arr + i)->val = i;
	}
	int gap = size / 2;
	for (int i = 1; i <= gap; ++i)
	{
		(Arr + i)->left = (Arr + (i << 1));
		(Arr + i)->right = i != gap ? (Arr + ((i << 1) + 1)) : (gap << 1) + 1 == size ? (Arr + size) : nullptr;
	}
	TreeNode *root = (Arr + 1);
	return root;
}

//遍历二叉树
//1.前序遍历
//递归法
void preTraverseTree(TreeNode *root)
{
	if (root == nullptr)
	{
		return;
	}
	cout << root->val;
	preTraverseTree(root->left);
	preTraverseTree(root->right);
}

//非递归法
void PreTraverseTree(TreeNode *root)
{
	//使用栈，基于后进先出的模式，所以左右孩子的顺序要倒过来放入栈中
	stack<TreeNode *> S;
	S.push(root);
	while (!S.empty())
	{
		TreeNode *top = S.top();
		cout << top->val;
		S.pop();
		if (top->right)
		{
			S.push(top->right);
		}
		if (top->left)
		{
			S.push(top->left);
		}
	}
}

//2.中序遍历
//递归法
void midTraverseTree(TreeNode *root)
{
	if (root == nullptr)
	{
		return;
	}
	midTraverseTree(root->left);
	cout << root->val;
	midTraverseTree(root->right);
}

//非递归
void MidTraverseTree(TreeNode *root)
{
	stack<TreeNode *> stack;
	while (root || !stack.empty())
	{
		while (root != nullptr)
		{
			stack.push(root);
			root = root->left;
		}
		root = stack.top();
		stack.pop();
		cout << root->val;
		root = root->right;
	}
}

//3.后序遍历
//递归法
void backTraverseTree(TreeNode *root)
{
	if (!root)
	{
		return;
	}
	backTraverseTree(root->left);
	backTraverseTree(root->right);
	cout << root->val;
}

//非递归
void BackTraverseTree(TreeNode *root)
{
	//按照"根右左"顺序访问结点，然后反转，反转后就是后序遍历的值
	std::vector<int> v;
	stack<TreeNode *> stack;
	stack.push(root);
	while (!stack.empty())
	{
		TreeNode *top = stack.top();
		stack.pop();
		v.push_back(top->val);
		if (top->left)
		{
			stack.push(top->left);
		}
		if (top->right)
		{
			stack.push(top->right);
		}
	}
	reverse(v.begin(), v.end());
	for (int i : v)
	{
		cout << i;
	}
}

//morris遍历
void morris(TreeNode *root)
{
	if (!root)
	{
		return;
	}
	TreeNode *cur = root;
	TreeNode *mostright = nullptr;
	while (cur)
	{
		mostright = cur->left;
		if (mostright)
		{
			while (mostright->right && mostright->right != cur)
			{
				mostright = mostright->right;
			}
			if (!mostright->right)
			{
				mostright->right = cur;
				cout << cur->val;
				cur = cur->left;
				continue;
			}
			else
			{
				mostright->right = nullptr;
			}
		}
		else
		{
			cout << cur->val;
		}
		cur = cur->right;
	}
}

//层次遍历
vector<vector<int>> rankTraverse(TreeNode *root)
{
	vector<vector<int>> V;
	if (!root)
	{
		return V;
	}
	deque<TreeNode *> dq;
	dq.push_back(root);
	// v.push_back(root->val);
	while (!dq.empty())
	{
		int count = dq.size();
		vector<int> v;
		while (count > 0)
		{
			TreeNode *head = dq.front();
			dq.pop_front();
			v.push_back(head->val);
			if (head->left)
			{
				dq.push_back(head->left);
			}
			if (head->right)
			{
				dq.push_back(head->right);
			}
			count--;
		}

		V.push_back(v);
	}
}

//锯齿型遍历
vector<vector<int>> zigzagLevelOrder(TreeNode *root)
{
	vector<vector<int>> V;
	if (!root)
		return V;
	//单队列
	deque<TreeNode *> dq;
	bool flag = true;
	//if true 尾结点出队，孩子结点左右顺序入队
	//if false 头结点出队，孩子结点右左顺序入队
	dq.push_front(root);
	while (!dq.empty())
	{
		int count = dq.size();
		vector<int> v;
		while (count > 0)
		{
			TreeNode *head;
			if (flag)
			{
				head = dq.back();
				dq.pop_back();
				if (head->left)
					dq.push_front(head->left);
				if (head->right)
					dq.push_front(head->right);
			}
			if (!flag)
			{
				head = dq.front();
				dq.pop_front();
				if (head->right)
					dq.push_back(head->right);
				if (head->left)
					dq.push_back(head->left);
			}
			count--;
		}
		flag = !flag;
		V.push_back(v);
	}
	return V;
}

//交换左右子树结点
void SwapTree(TreeNode *root)
{
	if (!root)
		return;
	SwapTree(root->left);
	SwapTree(root->right);
	if (!root->left && root->right)
	{
		root->left = new TreeNode();
		root->left->val = root->right->val;
		root->right = nullptr;
	}
	else if (!root->right && root->left)
	{
		root->right = new TreeNode();
		root->right->val = root->left->val;
		root->left = nullptr;
	}
	else if (root->right && root->left)
	{
		swap(root->left->val, root->right->val);
	}
	return;
}

//二叉树转链表
void flattern(TreeNode *root)
{
	if (!root)
	{
		return;
	}
	TreeNode *cur = root;
	TreeNode *rtemp = root; //指向右结点
	TreeNode *ltemp = root; //指向左结点
	while (cur->left || cur->right)
	{
		if (!cur->left) //左结点为空，就直接右移
		{
			cur = cur->right;
			continue;
		}
		//断开右子树结点，把左子树接到右子树上
		rtemp = cur->right;
		ltemp = cur->left;
		cur->right = ltemp;
		//记得要将左子树置为空
		cur->left = nullptr;
		//找到此时右子树上最后的一个结点
		while (ltemp->right)
		{
			ltemp = ltemp->right;
		}
		ltemp->right = rtemp;
		cur = cur->right;
	}
	return;
}

//验证BST
bool judge(TreeNode *root)
{
	if (!root)
	{
		return false;
	}
}
bool isValidBST(TreeNode *root)
{
	if (!root)
	{
		return true;
	}
	bool a = isValidBST(root->right);
	bool b = isValidBST(root->left);
	return root->left->val < root->val && root->right->val > root->val;
}

void getparentNum(TreeNode *root, TreeNode *parent, int key)
{
	if (!root)
	{
		return;
	}
	if (root->val == key)
	{ 
		if (root == parent)
		{
			return;
		}
		else
		{
			cout << "找到了" << endl;
			cout << parent->val;
		}
	}
	getparentNum(root->left, root, key);
	getparentNum(root->right, root, key);
}

//计算wpl最短带权路径
void getWPL(TreeNode *r, int depth, int &count)
{
	if (!r)
	{
		return;
	}
	if (!r->left && !r->right)
	{
		count += (depth * r->val);
		return;
	}
	getWPL(r->left, depth + 1, count);
	getWPL(r->right, depth + 1, count);
}

//求树中所有结点之和
int getSum(TreeNode* root){
	if(root==nullptr){
		return 0;
	}
	return root->val + getSum(root->left) + getSum(root->right);
}

int main(int argc, char const *argv[])
{
	cout << "输入结点数" << endl;
	int size = 0;
	cin >> size;
	TreeNode *Arr = new TreeNode[size + 1];
	TreeNode *arr = createBinaryTree(Arr, size); //头结点
	// cout<<"递归先序遍历"<<endl;
	// preTraverseTree(arr);
	// cout<<endl<<"非递归先序遍历"<<endl;
	// PreTraverseTree(arr);
	// cout<<endl<<"递归中序遍历"<<endl;
	// midTraverseTree(arr);
	// cout<<endl<<"非递归中序遍历"<<endl;
	// MidTraverseTree(arr);
	// cout<<endl<<"递归后序遍历"<<endl;
	// backTraverseTree(arr);
	// cout<<endl<<"非递归的后序遍历"<<endl;
	// BackTraverseTree(arr);
	// cout<<endl<<"morries遍历"<<endl;
	// morris(arr);
	cout << "层次遍历" << endl;
	vector<vector<int>> V = rankTraverse(arr);
	for (int i = 0; i < V.size(); i++)
	{
		for (int j = 0; j < V.at(i).size(); j++)
		{
			cout << V.at(i).at(j);
		}
		cout << endl;
	}
	cout << endl;
	cout << getSum(arr);
	// int count = 0;
	// getWPL(arr, 1, count);
	// cout << count;

	// cout << "二叉树的反转" << endl;
	// SwapTree(arr);
	// V = rankTraverse(arr);
	// for (int i = 0; i < V.size(); i++)
	// {
	// for (int j = 0; j < V.at(i).size(); j++)
	// {
	// cout << V.at(i).at(j);
	// }
	// cout << endl;
	// }
	// getparentNum(arr, arr, 6);
	delete[] Arr;
	return 0;
}