本文主要是介绍剑指offer——树的子结构（26题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：输入两棵二叉树A和B，判断B是不是A的子结构。
老生常谈，有关二叉树的题型解答，离不开遍历算法，此题又可以看成是用中序遍历改进法来解答。
其思路如下：
i、先从A树的根节点开始，一一与B树的节点对应匹配比较；
ii、如i不成功，则遍历根的左儿子，重复i过程；
iii、如ii不成功，则遍历根的右儿子，重复i过程。
代码实现如下：
#include<iostream>
#include<cmath>using namespace std;struct TreeNode {double val;TreeNode* left, *right;TreeNode(double x):val(x),left(nullptr),right(nullptr){}
};bool equal(TreeNode* root1, TreeNode* root2) {if (fabs(root1->val - root2->val) < 0.000001)return true;return false;
}bool doesTree1HaveTree2(TreeNode* root1, TreeNode* root2) {if (root2 == nullptr)//能到达B树的叶子节点的子节点，则返回truereturn true;if (root1 == nullptr)//能到达A树的叶子节点的子节点,说明还不能匹配成功，返回falsereturn false;if (!equal(root1, root2))//两节点值不相等，也返回falsereturn false;return doesTree1HaveTree2(root1->left, root2->left) && doesTree1HaveTree2(root1->right, root2->right);
}bool hasSubtree(TreeNode* root1, TreeNode* root2) {if (!root1 || !root2)return false;int result = false;if (equal(root1, root2))//从根节点判断，是否与root2匹配result = doesTree1HaveTree2(root1, root2);if (!result)//在根节点开始，与root2匹配不成功下，递归判断左儿子与root2是否匹配result = hasSubtree(root1->left, root2);if (!result)//在根节点且根的左子树，与root2匹配不成功下，递归判断右儿子与root2是否匹配result = hasSubtree(root1->right, root2);return result;
}
这篇关于剑指offer——树的子结构（26题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
