[PHP] 算法-二叉树的子结构判断的PHP实现

<div class="cnblogs_code">

1.子树的意思是包含了一个节点，就得包含这个节点下的所有节点,2.思路：

1.<span style="color: #000000">第一个递归：A和B两棵树，先在A中找到与B的根结点相同的点，如果A的根不是，那就递归A的左右子树来找

2.<span style="color: #000000">第二个递归：从两棵树的根结点开始进行比较，遍历的过程中，如果B树为空，则返回true;如果B不为空，A为空，返回false

A树的结点值与B树的不同，返回false;

短路运算符&&<span style="color: #000000"> ，递归A的左子树，B的左子树；递归A的右子树，B的右子树

HasSubtree(treeA,<span style="color: #000000">treeB)

<span style="color: #0000ff">if(treeA->val==treeB->val)<span style="color: #008000">//<span style="color: #008000">根结点相同

res=tree1HasTreeB(treeA.<span style="color: #000000">treeB)

<span style="color: #0000ff">if !<span style="color: #000000">res

res=HasSubtree(treeA->left.treeB)<span style="color: #008000">//<span style="color: #008000">第一层遍历

<span style="color: #0000ff">if !<span style="color: #000000">res

res=HasSubtree(treeA->right.treeB)<span style="color: #008000">//<span style="color: #008000">第一层遍历

<span style="color: #0000ff">return<span style="color: #000000"> res

tree1HasTreeB(treeA,<span style="color: #000000">treeB)

<span style="color: #008000">//<span style="color: #008000">顺序不能变

<span style="color: #0000ff">if treeB==<span style="color: #0000ff">null  <span style="color: #008000">//<span style="color: #008000">B到底的时候，就是true

<span style="color: #0000ff">return <span style="color: #0000ff">true

<span style="color: #0000ff">if treeA==<span style="color: #0000ff">null

<span style="color: #0000ff">return <span style="color: #0000ff">false<span style="color: #008000">//<span style="color: #008000">B没到底，A到底了，就是false

<span style="color: #0000ff">if treeA->val!=treeB->val <span style="color: #008000">//<span style="color: #008000">A和B的结点没对上

<span style="color: #0000ff">return <span style="color: #0000ff">false

<span style="color: #008000">//<span style="color: #008000">短路语法 ，如果前面的是false，直接返回false,后面不用走

<span style="color: #0000ff">return tree1HasTreeB(treeA->left,treeB->left)&&tree1HasTreeB(treeA->right,treeB->right)

<div class="cnblogs_code">

val = <span style="color: #008000">//<span style="color: #008000">构造两棵树

<span style="color: #800080">$node1=<span style="color: #0000ff">new TreeNode(1<span style="color: #000000">);

<span style="color: #800080">$node2=<span style="color: #0000ff">new TreeNode(2<span style="color: #000000">);

<span style="color: #800080">$node3=<span style="color: #0000ff">new TreeNode(3<span style="color: #000000">);

<span style="color: #800080">$node4=<span style="color: #0000ff">new TreeNode(4<span style="color: #000000">);

<span style="color: #800080">$node5=<span style="color: #0000ff">new TreeNode(5<span style="color: #000000">);

<span style="color: #800080">$treeA=<span style="color: #800080">$node1<span style="color: #000000">;

<span style="color: #800080">$node1->left=<span style="color: #800080">$node2<span style="color: #000000">;

<span style="color: #800080">$node1->right=<span style="color: #800080">$node3<span style="color: #000000">;

<span style="color: #800080">$node3->left=<span style="color: #800080">$node4<span style="color: #000000">;

<span style="color: #800080">$node3->right=<span style="color: #800080">$node5<span style="color: #000000">;
<span style="color: #008000">//<span style="color: #008000">var_dump($treeA);
<span style="color: #800080">$node6=<span style="color: #0000ff">new TreeNode(3<span style="color: #000000">);

<span style="color: #800080">$node7=<span style="color: #0000ff">new TreeNode(4<span style="color: #000000">);

<span style="color: #800080">$node6->left=<span style="color: #800080">$node7<span style="color: #000000">;

<span style="color: #800080">$treeB=<span style="color: #800080">$node6<span style="color: #000000">;

<span style="color: #008000">//<span style="color: #008000">var_dump($treeB);
<span style="color: #0000ff">function HasSubtree(<span style="color: #800080">$pRoot1,<span style="color: #800080">$pRoot2<span style="color: #000000">){

<span style="color: #800080">$res=<span style="color: #0000ff">false<span style="color: #000000">;

<span style="color: #0000ff">if(<span style="color: #800080">$pRoot1==<span style="color: #0000ff">null || <span style="color: #800080">$pRoot2==<span style="color: #0000ff">null) <span style="color: #0000ff">return <span style="color: #800080">$res<span style="color: #000000">;

<span style="color: #0000ff">if(<span style="color: #800080">$pRoot1->val==<span style="color: #800080">$pRoot2->val) <span style="color: #800080">$res=tree1HasTree2(<span style="color: #800080">$pRoot1,<span style="color: #800080">$pRoot2<span style="color: #000000">);

<span style="color: #0000ff">if(!<span style="color: #800080">$res) <span style="color: #800080">$res=HasSubtree(<span style="color: #800080">$pRoot1->left,<span style="color: #800080">$pRoot2<span style="color: #000000">);

<span style="color: #0000ff">if(!<span style="color: #800080">$res) <span style="color: #800080">$res=HasSubtree(<span style="color: #800080">$pRoot1->right,<span style="color: #800080">$pRoot2<span style="color: #000000">);

<span style="color: #0000ff">return <span style="color: #800080">$res<span style="color: #000000">;

}

<span style="color: #0000ff">function tree1HasTree2(<span style="color: #800080">$treeA,<span style="color: #800080">$treeB<span style="color: #000000">){

<span style="color: #0000ff">if(<span style="color: #800080">$treeB==<span style="color: #0000ff">null) <span style="color: #0000ff">return <span style="color: #0000ff">true<span style="color: #000000">;

<span style="color: #0000ff">if(<span style="color: #800080">$treeA==<span style="color: #0000ff">null) <span style="color: #0000ff">return <span style="color: #0000ff">false<span style="color: #000000">;

<span style="color: #0000ff">if(<span style="color: #800080">$treeA->val!=<span style="color: #800080">$treeB->val) <span style="color: #0000ff">return <span style="color: #0000ff">false<span style="color: #000000">;

<span style="color: #0000ff">return tree1HasTree2(<span style="color: #800080">$treeA->left,<span style="color: #800080">$treeB->left)&&tree1HasTree2(<span style="color: #800080">$treeA->right,<span style="color: #800080">$treeB-><span style="color: #000000">right);

}

<span style="color: #008080">var_dump(HasSubtree(<span style="color: #800080">$treeA,<span style="color: #800080">$treeB));

（编辑：安卓应用网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!