首页 > 代码库 > 100. Same Tree(LeetCode)

100. Same Tree(LeetCode)

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

在下写的代码比较长,但是思路是很简单的,因为先序遍历和中序遍历可以确定一棵树,只需比较两颗树的先序和中序即可,但是还要注意一点,为空节点赋一个值,要不然在树不等的情况下,中序和先序也会相等。比如[1 1]和[1 NULL 1]。


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
   vector<int> pre;
	vector<int> mid;
	bool isSameTree(TreeNode* p, TreeNode* q) {
		vector<int> ppvet;
		vector<int> qpvet;
		vector<int> pmvet;
		vector<int> qmvet;
		prem(p);
		ppvet = pre;
		pre.clear();
		prem(q);
		qpvet = pre;
		midd(p);
		pmvet = mid;
		mid.clear();
		midd(q);
		qmvet = mid;
		/*for (int i = 0; i < pmvet.size(); i++)
			cout << pmvet[i] << endl;
		for (int i = 0; i < qmvet.size(); i++)
			cout << qmvet[i] << endl; */
		if (ppvet == qpvet&&pmvet == qmvet)
			return true;
		else
			return false;


	}
	void prem(TreeNode * root)
	{
		if (root == NULL)
			return ;
		pre.push_back(root->val);
		if (root->left)
		{
			pre.push_back(root->left->val);
			prem(root->left);
		}
		else
			{
			pre.push_back(-1);
			prem(root->left);
		}
		if (root->right)
		{
			pre.push_back(root->right->val);
			prem(root->right);
		}
		else
			{
			pre.push_back(-1);
			prem(root->right);
		}
	}
	void midd(TreeNode * root)
	{
		if (root == NULL)
			return;
		if (root->left)
		{
			mid.push_back(root->left->val);
			midd(root->left);
		}
		else
			{
			mid.push_back(-1);
			midd(root->left);
		}
		mid.push_back(root->val);
		if (root->right)
		{
			mid.push_back(root->right->val);
			midd(root->right);
		}
		else
		{
			mid.push_back(-1);
			midd(root->right);
		}
	}
};

  

 

100. Same Tree(LeetCode)