1 package data.structure;
2
3 import java.util.ArrayList;
4
5 public class TreeNode {
6 public int val;
7 public TreeNode left;
8 public TreeNode right;
9 public TreeNode(int x) { val = x; }
10
11 public static TreeNode makeTree(Integer[] trees) {
12 if (trees.length == 0)
13 return null;
14 TreeNode[] treeNodes = new TreeNode[trees.length + 1];
15 for (int i = 1; i < treeNodes.length; i++) {
16 if (trees[i - 1] == null) {
17 treeNodes[i] = null;
18 } else {
19 treeNodes[i] = new TreeNode(trees[i - 1]);
20 }
21 }
22
23 TreeNode treeNode = null;
24 //这个只适用于完全二叉树
25 // for (int i = 1; i < treeNodes.length; i++) {
26 // treeNode = treeNodes[i];
27 // if (treeNode == null) continue;
28 // if (2 * i < treeNodes.length)
29 // treeNode.left = treeNodes[2 * i];
30 // if (2 * i + 1 < treeNodes.length)
31 // treeNode.right = treeNodes[2 * i + 1];
32 // }
33 for (int i = 1, index = 2; i < treeNodes.length && index < treeNodes.length; i++) {
34 treeNode = treeNodes[i];
35 if (treeNode == null) continue;
36 treeNode.left = treeNodes[index];
37 if (index + 1 < treeNodes.length)
38 treeNode.right = treeNodes[index + 1];
39 index += 2;
40 }
41 return treeNodes[1];
42 }
43
44 //中序遍历（左->根->右）
45 public static ArrayList<Integer> middleTraverse(TreeNode treeNode) {
46 ArrayList<Integer> arrayList = new ArrayList<>();
47 if (treeNode == null) {
48 arrayList.add(null);
49 }else if (treeNode.left == null && treeNode.right == null) {
50 arrayList.add(treeNode.val);
51 } else {
52 arrayList.addAll(middleTraverse(treeNode.left));
53 arrayList.add(treeNode.val);
54 arrayList.addAll(middleTraverse(treeNode.right));
55 }
56 return arrayList;
57 }
58
59 //前序遍历（根->左->右）
60 public static ArrayList<Integer> beforeTraverse(TreeNode treeNode) {
61 ArrayList<Integer> arrayList = new ArrayList<>();
62 if (treeNode == null) {
63 arrayList.add(null);
64 }else if (treeNode.left == null && treeNode.right == null) {
65 arrayList.add(treeNode.val);
66 } else {
67 arrayList.add(treeNode.val);
68 arrayList.addAll(beforeTraverse(treeNode.left));
69 arrayList.addAll(beforeTraverse(treeNode.right));
70 }
71 return arrayList;
72 }
73
74 //后序遍历（左->右->根）
75 public static ArrayList<Integer> afterTraverse(TreeNode treeNode) {
76 ArrayList<Integer> arrayList = new ArrayList<>();
77 if (treeNode == null) {
78 arrayList.add(null);
79 }else if (treeNode.left == null && treeNode.right == null) {
80 arrayList.add(treeNode.val);
81 } else {
82 arrayList.addAll(afterTraverse(treeNode.left));
83 arrayList.addAll(afterTraverse(treeNode.right));
84 arrayList.add(treeNode.val);
85 }
86 return arrayList;
87 }
88
89 //层序遍历
90 public static ArrayList<Integer> sequenceTraverse(TreeNode root) {
91 ArrayList<Integer> arrayList = new ArrayList<>();
92 ArrayList<TreeNode> treeNodes = new ArrayList<>();
93 treeNodes.add(root);
94 arrayList.add(root.val);
95 while (treeNodes.size() > 0) {
96 ArrayList<TreeNode> subTreeNodes = new ArrayList<>();
97 for (TreeNode value : treeNodes) {
98 if (value.left != null || value.right != null) {
99 if (value.left != null) {
100 subTreeNodes.add(value.left);
101 arrayList.add(value.left.val);
102 } else {
103 arrayList.add(null);
104 }
105 if (value.right != null) {
106 subTreeNodes.add(value.right);
107 arrayList.add(value.right.val);
108 } else {
109 arrayList.add(null);
110 }
111 }
112 }
113 treeNodes = subTreeNodes;
114 }
115 return arrayList;
116 }
117 }
1 package data.structure;
2
3 import java.util.ArrayList;
4
5 public class ListNode {
6 public int val;
7 public ListNode next;
8 public ListNode(int x) {
9 val = x;
10 next = null;
11 }
12
13 //创建单链表
14 public static ListNode makeNode(int[] nums) {
15 if (nums.length == 0) return null;
16 ListNode listNode = new ListNode(nums[0]);
17 ListNode head = listNode;
18 for (int i = 1; i < nums.length; i++) {
19 ListNode node = new ListNode(nums[i]);
20 listNode.next = node;
21 listNode = node;
22 }
23 return head;
24 }
25
26 //创建循环链表
27 public static ListNode makeNode(int[] nums, int pos) {
28 if (nums.length == 0) return null;
29 ListNode[] listNodes = new ListNode[nums.length];
30 for (int i = 0; i < nums.length; i++) {
31 listNodes[i] = new ListNode(nums[i]);
32 }
33
34 ListNode listNode = listNodes[0];
35 for (int i = 1; i < listNodes.length; i++) {
36 listNode.next = listNodes[i];
37 listNode = listNodes[i];
38 }
39 if (pos >= 0 && pos < nums.length) {
40 listNode.next = listNodes[pos];
41 }
42 return listNodes[0];
43 }
44
45 //创建两条相交链表
46 public static ListNode[] makeIntersectNode(int[] listA, int skipA, int[] listB, int skipB) {
47 if (listA.length == 0 || listB.length == 0) return null;
48 ListNode[] nodesA = new ListNode[listA.length];
49 for (int i = 0; i < nodesA.length; i++) {
50 nodesA[i] = new ListNode(listA[i]);
51 }
52 ListNode nodeA = nodesA[0];
53 for (int i = 1; i < nodesA.length; i++) {
54 nodeA.next = nodesA[i];
55 nodeA = nodesA[i];
56 }
57
58 ListNode[] nodesB = new ListNode[listB.length];
59 for (int i = 0; i < nodesB.length; i++) {
60 nodesB[i] = new ListNode(listB[i]);
61 }
62 ListNode nodeB = nodesB[0];
63 for (int i = 1; i < nodesB.length; i++) {
64 nodeB.next = nodesB[i];
65 nodeB = nodesB[i];
66 }
67
68 if (skipA < listA.length && skipB < listB.length && listA[skipA] == listB[skipB]) {
69 nodesB[skipB].next = nodesA[skipA];
70 }
71
72 ListNode[] nodes = new ListNode[2];
73 nodes[0] = nodesA[0];
74 nodes[1] = nodesB[0];
75 return nodes;
76 }
77
78 //遍历链表
79 public static ArrayList<Integer> traverse(ListNode head) {
80 ArrayList<Integer> arrayList = new ArrayList<>();
81 while (head != null) {
82 arrayList.add(head.val);
83 head = head.next;
84 }
85 return arrayList;
86 }
87 }