剑指Offer:树的子结构

题目

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

分析

树不同于指针,树中的指针操作更多也更复杂。

判断B是不是A的子结构,我们可以分为两步,第一步,在树A中找到树B的根节点的值一样的节点S。第二步,树A中以S为根节点的子树是否包含和树B一样的结构。

第一步,查找节点S的过程实际上就是树的遍历。

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
34
35
36
37
38
39
40
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {
public boolean DoesHaveTree2(TreeNode root1,TreeNode root2) {
if (root2 == null)
return true;
if (root1 == null)
return false;

if (root1.val != root2.val)
return false;
return DoesHaveTree2(root1.left, root2.left) && DoesHaveTree2(root1.right, root2.right);
}


public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result = false;

if (root1 != null && root2 != null) {
if (root1.val == root2.val)
result = DoesHaveTree2(root1, root2);
if (!result)
result = DoesHaveTree2(root1.left, root2);
if (!result)
result = DoesHaveTree2(root1.right, root2);
}
return result;
}
}

在上述代码中,我们递归的调用HasSubtree遍历二叉树A。如果发现某一节点的值和树B的头节点的值相同,则调用DoesHaveTree2进行第二步的判断。

第二步同样用递归思想来考虑,如果节点S的值和树B的根节点不同,则以S为根节点的子树和树B肯定不具有相同的节点;如果他们的值相同,则递归的判断他们各自的左右节点的值是否相同。

有收获再赞赏哦🤭
------ 本文结束感谢您的阅读-------------
0%