树的子结构

题目

牛客网

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

解题思路

1. 遍历查找相等根节点
2. 通过递归查找当前根节点下是否包含子树 root2

1. public boolean HasSubtree(TreeNode root1, TreeNode root2) {
2. if (root2 == null) {
3. return false;
4. }

6. LinkedList<TreeNode> pipeline = new LinkedList<>();
7. pipeline.addLast(root1);

9. while (!pipeline.isEmpty()) {
10. TreeNode node = pipeline.pop();
11. if (node == null) {
12. continue;
13. }

15. pipeline.addLast(node.left);
16. pipeline.addLast(node.right);

18. if (node.val == root2.val && isSub(node, root2)) {
19. return true;
20. }
21. }

23. return false;
24. }

26. private boolean isSub(TreeNode root1, TreeNode root2) {
27. if (root1 == null && root2 == null) {
28. return true;
29. }

31. if (root1 == null) {
32. return false;
33. }

35. if (root2 == null) {
36. return true;
37. }

39. if (root1.val == root2.val) {
40. return isSub(root1.left, root2.left) && isSub(root1.right, root2.right);
41. } else {
42. return false;
43. }

45. }