剑指offer(11) 合并链表 树的子结构
题目:
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
思路:
递归
每次处理当前节点之后,递归处理下一个节点。
非递归
每次处理节点前判断两个链表的当前节点的大小,当某个链表遍历完之后,将另一个链表加到当前链表的最后一个节点。
代码:
复制代码
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66//递归 public ListNode Merge(ListNode list1,ListNode list2) { if (list1==null&&list2==null) { return null; } if(list1 == null){ return list2; } if(list2 == null){ return list1; } ListNode newHead = null; if (list1.val<list2.val) { newHead = list1; newHead.next = Merge(newHead.next,list2); }else { newHead = list2; newHead.next = Merge(newHead.next,list1); } return newHead; } //非递归 public ListNode Merge1(ListNode list1,ListNode list2) { if (list1==null&&list2==null) { return null; } if(list1 == null){ return list2; } if(list2 == null){ return list1; } ListNode newHead = new ListNode(-1); ListNode head = newHead; //利用新的节点去合并两条链表,最终返回的是 newHead 。 //如果返回的是 head ,那么只是返回合并之后的最后一个节点 while (list1!=null&&list2!=null) { if (list1.val>=list2.val) { head.next = list2; list2 = list2.next; }else { head.next = list1; list1=list1.next; } head = head.next; } if (list1!=null) { head.next = list1; } if (list2!=null) { head.next=list2; } return newHead.next; }
题目:
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
思路:
2
复制代码
1
23 4 与 4
4 5 2 7 3 7 B是否是A的子结构?
先遍历头节点,如果头节点不相同,递归调用左右子节点,当找到A中某个节点和B的头节点相同。判断 子节点是否相同,如果子节点都相同,就返回true。
代码:
复制代码
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
41
42
43
44public boolean HasSubtree(TreeNode root1, TreeNode root2) { boolean result = false; if (root1 != null && root2 != null) { if (root1.val == root2.val) { result = DoesTree1HaveTree2(root1, root2); //判断这两个节点的子节点是否相同 } if (!result) { result = HasSubtree(root1.left, root2); } if (!result) { result = HasSubtree(root1.right, root2); } } return result; } public boolean DoesTree1HaveTree2(TreeNode root1, TreeNode root2) { //如果Tree2已经遍历完了都能对应的上,返回true if (root2 == null) { return true; } //如果Tree2还没有遍历完,Tree1却遍历完了。返回false if (root1 == null) { return false; } //如果其中有一个点没有对应上,返回false if (root1.val != root2.val) { return false; } //如果根节点对应的上,那么就分别去子节点里面匹配 return DoesTree1HaveTree2(root1.left, root2.left) && DoesTree1HaveTree2(root1.right, root2.right); }
最后
以上就是羞涩钢笔最近收集整理的关于剑指Offer(11) 合并链表 树的子结构的全部内容,更多相关剑指Offer(11)内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复