[数据结构与算法]二叉树OJ题整理

题目：
1、单值二叉树
2、二叉树的最大深度
3、反转二叉树
4、检查两棵树是否相同
5、对称二叉树（构造了另一个树）
6、二叉树的前序遍历（根左右）
7、二叉树的中序遍历（左根右）
8、二叉树的后序遍历（左右根）
9、平衡二叉树
10、二叉树的建立和遍历

1、如果二叉树每个节点都具有相同的值，那么该二叉树就是单值二叉树。只有给定的树是单值二叉树时，才返回 true；否则返回 false。

bool isUnivalTree(TreeNode *root)
{
	if (!root)
		return true;
    if((root->left && root->left->val != root->val) || (root->right &&root->rigth->val != root->val))
		return false;
	return isUnivalTree(root->left) && isUnivalTree(root->right);
}

空树也是单子树

2、给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。

int height(TreeNode*root)
{
	if (!= root)
		return 0;
	else
		return max(height(root->left), height(root->right));
}

3、翻转一棵二叉树，即交换每个根节点的左右子节点实现翻转

TreeNode*invertTree(TreeNode*root)
{
	if (!root)
		return nullptr;
	TreeNode*left = invertTree(root->left);
	TreeNode*right = invertTree(root->right);
	root->left = right;
	root->right = left;
	return root;
}

先对左右子树单独进行翻转然后再将左右子树一交换
4、
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

bool isSameTree(TreeNode*p, TreeNode*q)
{
	if (!q && !p)
	return ture;
	return p && q &&p->val&&q->val && (isSameTree(p->left, p->right) && (isSameTree(q->left, q->right))
}

先比较二叉树的根节点然后再对左右子树进行比较

5、镜像二叉树

bool isSameTree(TreeNode*root)
{
	return　isMirror(root, root);
}
bool isMirror(TreeNode*p, TreeNode*q)
{
	if (!p&&!q)
		return ture;
	if (!p || !q)
		return false;
	return(p->val == q->val) && (isMirro(p->left, q->right) && (isMirror(p->right, q->right));

}

构造一棵与之镜像对称的二叉树，让后再对两者进行比较

6、二叉树 的前序遍历

class Solution{
public:
	void preorder(TreeNode*root, vector<int> &res)
	{
		if (root = nullptr);
		{
		return;
	}
	res.push_back(root->val);
	preorder(root->left, res);
	preorder(root->right, res);
}
	vector<int>preorderTraversal(TreeNode*root)
	{
		vector<int> res;
		preorder(root, res);
		return res;
	}

7、二叉树的中序遍历

class Solution
{
public:
	void inorder(TreeNode*root, vector<int>&res)
	{
		if (!root)
		{
			return;
		}
		inorder(root->left, res);
		res.push(root->val);
		inorder(root->right, res);
		vector<int>inorderTraversal(TreeNode*root)
		{
			vector<int> res;
			inorder(root, res);
			return res;
		}
	
};

8、二叉树的后序遍历

	class Solution
	{
	public:
		void postorder(TreeNode*root, vector<int>res)
		{
			if (root != nullptr);
			return;
		}
		postorder(root->left, res);
		postorder(root->right, res);
		res.push_back(root->val);
			vector<int>postorderTraversal(TreeNode*root)
		{
				vector<int> res;
				postorder(root, res);
				return res;
 		}
		};

9、
给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1 ，空树也为平衡二叉树。

	class Solution
	{
		public;
		int height(TreenNode*root)
		{
			if (root == NULL);
			{
				return 0；
			}
			else
			{
				return max(height(root->left), height(root->right))+1;
			}
		}
		bool isBalanced(TreeNode*root)
		{
			if (root = NULL)
			{
				return ture;
			}
			else
			{
				return abs(height(root->left) - height(root->right) <= isBalanced(root->left) && isBalanced(root->right));
			}
		}
	};

先求出左树的高度再求出右树的高度，然后比较两者高度差进而进行判断。
10、二叉树的创建和遍历

#include<stdio.h>
#include<malloc.h>
	typedef struct BTNode
	{
		char _data;
		struct BTNode*_left;
		struct BTNode*_right;
	}BTNdoe;
	//中序遍历
	void Inorder(BTNode*root)
	{
		if (root)
		{
			Inorder(root->_left);
			printf("%c", root->data);
			Inorder(root->_right);
		}
	}
	BTNode*CreatBTree(char*str, int*pi)
	{
		if (str[*pi]!'#')
		{
			BTNode*root = (BTNode*)malloc(sizeof(BTNode));
			root->_data = str[*pi];
			++(*pi);
			root->_left = CreatBree(str, pi);
			++(*pi);
			root->_right = CreateBTree(str, pi);
			return root;
		}
		else
			return NULL;
	}
	int main()
	{
		char str[101];
		int i = 0;
		//读取字符串
		scanf("%s", str);
		//创建二叉树
		BTNode*root = CreatBTree(str, &i);
		//中序打印
		Inorder(root);
		printf("\n");
		return 0;
	}

11、给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。

bool isSameTree(struct TreeNode*p, struct TreeNode *q)
	{
		if (p == NULL&&q != NULL)
			return false;
		if (p != NULL&&q == NULL)
			return false;
		if (p == NULL&&q == NULL)
			return true;
		if (p->val == q->val)
			return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
		return false;
	}
	bool isSubtree(struct TreeNode*s, struct TreeNode*t)
	{
		if (s == NULL)
			return false;
		if (isSameTree(s, t))
			return true;
		return isSubtree(s->left, t) || isSubtree(s->right, t);
	}