判断一棵树是否是另一棵树的子树

时间:2022-08-26 20:50:46

问题

判断一棵树是否是另一棵树的子树,如图

判断一棵树是否是另一棵树的子树

思路

问题分两步:

  • 找值相同的根结点(遍历解决)
  • 判断两结点是否包含(递归:值、左孩子、右孩子分别相同)

树节点定义

struct TreeNode
{
int val;
TreeNode
*next;
TreeNode(
int v) : val(v), next(NULL) {}
};

代码

bool IsPart(TreeNode *root1, TreeNode *root2)
{
if (root2 == NULL)
return true;
if (root1 == NULL)
return false;
if (root1->val != root2->val)
return false;
return IsPart(root1->left, root2->left) &&
IsPart(root1
->right, root2->right);
}
bool IsPartTree(TreeNode *root1, TreeNode *root2)
{
bool result = false;
if (root1 != NULL && root2 != NULL)
{
if (root1->val == root2->val)
result
= IsPart(root1, root2);
if (!result)
result
= IsPartTree(root1->left, root2);
if (!result)
result
= IsPartTree(root1->right, root2);
}
return result;
}

执行

判断一棵树是否是另一棵树的子树判断一棵树是否是另一棵树的子树
#include <iostream>
#include
<stack>
using namespace std;
struct TreeNode
{
int val;
TreeNode
*left;
TreeNode
*right;
TreeNode(
int v) : val(v), left(NULL), right(NULL) {}
};
bool IsPart(TreeNode *root1, TreeNode *root2)
{
if (root2 == NULL)
return true;
if (root1 == NULL)
return false;
if (root1->val != root2->val)
return false;
return IsPart(root1->left, root2->left) &&
IsPart(root1
->right, root2->right);
}
bool IsPartTree(TreeNode *root1, TreeNode *root2)
{
bool result = false;
if (root1 != NULL && root2 != NULL)
{
if (root1->val == root2->val)
result
= IsPart(root1, root2);
if (!result)
result
= IsPartTree(root1->left, root2);
if (!result)
result
= IsPartTree(root1->right, root2);
}
return result;
}
TreeNode
* createTree1()
{
TreeNode
*root = new TreeNode(1);
TreeNode
*p1 = new TreeNode(2);
TreeNode
*p2 = new TreeNode(3);
TreeNode
*p3 = new TreeNode(4);
TreeNode
*p4 = new TreeNode(5);
root
->left = p1;
root
->right = p2;
p2
->left = p3;
p2
->right = p4;
return root;
}
TreeNode
* createTree2()
{
TreeNode
*root = new TreeNode(1);
TreeNode
*p1 = new TreeNode(2);
TreeNode
*p2 = new TreeNode(3);
root
->left = p1;
root
->right = p2;
return root;
}


void deleteTree(TreeNode *root)
{
if (root != NULL)
{
delete(root
->left);
delete(root
->right);
delete root;
root
= NULL;
}
}
int main()
{
TreeNode
*root1 = createTree1();
TreeNode
*root2 = createTree2();
cout
<< IsPartTree(root1, root2) << endl;
deleteTree(root1);
deleteTree(root2);
}
View Code

 

推荐

算法与数据结构索引