假设我们有两个二叉树;我们必须定义一个函数来检查它们是否相同。我们知道,当二叉树在结构上相同并且节点具有相同的值时,它们被视为相同。
因此,如果输入类似于[1,2,3],[1,2,3],则输出为True
为了解决这个问题,我们将遵循以下步骤-
定义一个名为isSameTree的函数,它将使用两个树节点p和q
如果p与NULL相同,而q与NULL相同,则-
返回真
如果p与NULL相同或q与NULL相同,则-
返回假
如果p的val与p的val相同,并且isSameTree(p的左侧,q的左侧)为true,并且isSameTree(p的右侧,q的右侧)为true,则
返回真
返回假
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = NULL; right = NULL; } }; void insert(TreeNode **root, int val){ queue<TreeNode*> q; q.push(*root); while(q.size()){ TreeNode *temp = q.front(); q.pop(); if(!temp->left){ if(val != NULL) temp->left = new TreeNode(val); else temp->left = new TreeNode(0); return; } else{ q.push(temp->left); } if(!temp->right){ if(val != NULL) temp->right = new TreeNode(val); else temp->right = new TreeNode(0); return; } else{ q.push(temp->right); } } } TreeNode *make_tree(vector<int> v){ TreeNode *root = new TreeNode(v[0]); for(int i = 1; i<v.size(); i++){ insert(&root, v[i]); } return root; } class Solution { public: bool isSameTree(TreeNode *p, TreeNode* q){ if (p == NULL && q == NULL) return true; if (p == NULL || q == NULL) return false; if (p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right)) return true; return false; } }; main(){ Solution ob; vector<int> v = {1,2,3}, v1 = {1,2,3}; TreeNode *root1 = make_tree(v); TreeNode *root2 = make_tree(v1); cout << (ob.isSameTree(root1, root2)); }
{1,2,3}, {1,2,3}
输出结果
1