输入两棵二叉树A和B，判断B是不是A的子结构
C#实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#region 树的子结构
/// 输入两棵二叉树A和B，判断B是不是A的子结构
///
public
static
bool
HasSubTree(BinaryTreeNode pRoot1, BinaryTreeNode pRoot2)
{
bool
result =
false
;
if
(pRoot1 !=
null
&& pRoot2 !=
null
)
{
if
(pRoot1.value == pRoot2.value)
result = DoesTree1HaveTree2(pRoot1, pRoot2);
if
(!result)
result = HasSubTree(pRoot1.left, pRoot2);
if
(!result)
result = HasSubTree(pRoot1.right, pRoot2);
}
return
result;
}
public
static
bool
DoesTree1HaveTree2(BinaryTreeNode pRoot1, BinaryTreeNode pRoot2)
{
if
(pRoot2 ==
null
)
return
true
;
if
(pRoot1 ==
null
)
return
false
;
if
(pRoot1.value != pRoot2.value)
return
false
;
return
DoesTree1HaveTree2(pRoot1.left, pRoot2.left) &&
DoesTree1HaveTree2(pRoot1.right, pRoot2.right);
}
#endregion
|
Java实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
/**
* 树的子结构 输入两棵二叉树A和B，判断B是不是A的子结构
*
* @param pRoot1
* @param pRoot2
* @return
*/
public
static
boolean
hasSubTree(BinaryTreeNode pRoot1, BinaryTreeNode pRoot2) {
boolean
result =
false
;
if
(pRoot1 !=
null
&& pRoot2 !=
null
) {
if
(pRoot1.value == pRoot2.value)
result = doesTree1HaveTree2(pRoot1, pRoot2);
if
(!result)
result = hasSubTree(pRoot1.left, pRoot2);
if
(!result)
result = hasSubTree(pRoot1.right, pRoot2);
}
return
result;
}
private
static
boolean
doesTree1HaveTree2(BinaryTreeNode pRoot1, BinaryTreeNode pRoot2) {
if
(pRoot2 ==
null
)
return
true
;
if
(pRoot1 ==
null
)
return
false
;
if
(pRoot1.value != pRoot2.value)
return
false
;
return
doesTree1HaveTree2(pRoot1.left, pRoot2.left) && doesTree1HaveTree2(pRoot1.right, pRoot2.right);
}
|
Python实现：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
@staticmethod
def
hasSubTree(pRoot1, pRoot2):
"""
树的子结构 输入两棵二叉树A和B，判断B是不是A的子结构
:param pRoot1:
:param pRoot2:
:return:
"""
result
=
False
if
pRoot1 !
=
None
and
pRoot2 !
=
None
:
if
pRoot1.value
=
=
pRoot2.value:
result
=
BinaryTree.doesTree1HaveTree2(pRoot1, pRoot2)
if
not
result:
result
=
BinaryTree.hasSubTree(pRoot1.left, pRoot2)
if
not
result:
result
=
BinaryTree.hasSubTree(pRoot1.right, pRoot2)
return
result
@
staticmethod
def
doesTree1HaveTree2(pRoot1, pRoot2):
if
pRoot2
=
=
None
:
return
True
if
pRoot1
=
=
None
:
return
False
if
pRoot1.value !
=
pRoot2.value:
return
False
return
BinaryTree.doesTree1HaveTree2(pRoot1.left,
pRoot2.left) \
and
BinaryTree.doesTree1HaveTree2(pRoot1.right,
pRoot2.right)
|
本文转自 许大树 51CTO博客，原文链接：http://blog.51cto.com/abelxu/1972365，如需转载请自行联系原作者
