如果f是由有序树t转换而来的二叉树,

　　进入两个二叉树A和B，判断B是否是A的子结构。

　　我们规定空树不是任何树的子结构。

　　样品

　　树a:

　　八

　　/\

　　8 7

　　/\

　　9 2

　　/\

　　7树B:

　　八

　　/\

　　9返回true，因为B是a的子结构。

　　想法(二叉树，递归)

　　代码分为两部分：

　　遍历树a中所有非空节点r；判断树A中以R为根节点的子树是否包含与树B相同的结构，我们从根节点开始匹配；对于第一部分，我们可以直接递归遍历树A。当我们遇到非空节点时，我们会做出第二部分的判断。

　　对于第二部分，我们从根节点同时遍历两个子树：

　　如果树B中的节点为空，则表示当前分支匹配，返回true；如果树A中的节点为空，但树B中的节点不为空，则表示没有匹配，为false被返回；如果两个节点都不为空，但值不同，则说明不匹配，为false被返回；否则匹配当前点，然后分别递归判断左子树和右子树是否匹配。时间复杂度

　　最坏的情况下，我们要递归判断树A中的每个节点，最坏的情况下每个判断需要遍历树B中的所有节点。

　　所以时间复杂度是，其中树A的节点数是树b的节点数。

　　代码/* *

　　*二叉树节点的定义。

　　*结构树节点{

　　* int val

　　* TreeNode * left

　　* TreeNode * right

　　* TreeNode(int x) : val(x)，left(NULL)，right(NULL) {}

　　* };

　　*/

　　类别解决方案{

　　公共：

　　bool has sub tree(TreeNode * proof 1，TreeNode * proof 2){

　　如果(！pRoot1 ！pRoot2)返回false//如果A树或B树为空，则返回false

　　if(is same(proof 1，pRoot2))返回true//从根节点开始匹配

　　//如果从根节点不匹配，我们就递归到A的左右子树进行匹配。

　　if(has subtree(proof 1-left，proof 2) has subtree(proof 1-right，proof 2))返回true

　　}

　　bool is same(TreeNode * proof 1，TreeNode * pRoot2)

　　{

　　如果(！pRoot2)返回true//B树为空，匹配成功，递归终点结束。

　　如果(！proof 1 proof 1-val！=pRoot2- val)返回false

　　//否则表示当前点匹配，然后分别递归判断左子树和右子树是否匹配。

　　return is name(proof 1-left，proof 2-left)is name(proof 1-right，proof 2-right)；

　　}

　　};

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。