题目来源
今天做了个题:
将一个链表里的数据组装树形结构,链表里的数据已经满足树形结构要求
这道题描述的很简单,但是有很多种情况。他只说了链表数据满足树形结构要求,并没有说明数据到底是什么样的,也就是题目参数具有多样性,这样其实我们给出一种解决方案就可以。而且也只要求将链表转换为树,并没有说是什么树。所以这道题说难也难,说简单也简单。
解题思路
最近也将平衡二叉树的原理看了一下,正好借着这道题将代码手写一下。
我写了一个平衡二叉树的插入方法。我们不管链表里面的数据是如何排序的,我们只要调用树的插入方法即可。在插入方法内部实现树的平衡。
所以我们这道题也就转换成了手写平衡二叉树的插入过程。
代码实现
平衡二叉树
首先我们需要定义平衡二叉树的数据结构,在这里我们就用 int 类型来简单实现。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
class AVLTreeNode { int val; int height = -1; AVLTreeNode left; AVLTreeNode right;
public AVLTreeNode() { }
public AVLTreeNode(int val) { this.val = val; }
}
|
接下来我们定义这个平衡二叉树中所需用到的方法:
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
| class AVLTree { AVLTreeNode head; private static int Height(AVLTreeNode avlTreeNode) { if (avlTreeNode == null) { return -1; } else { return avlTreeNode.height; } }
public AVLTreeNode add(int value) { head = insert(head, value); return head; } private AVLTreeNode insert(AVLTreeNode root, int val) { ... ... } }
|
我们知道,在平衡二叉树中,有四种调整情况。分别为 LL型,LR 型,RL 型,RR 型。
所以需要将这四个方法提前写明:
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
|
public AVLTreeNode LL(AVLTreeNode node) { AVLTreeNode result = node.left; node.left = result.right; result.right = node; node.height = Math.max(Height(node.left), Height(node.right)) + 1; result.height = Math.max(Height(result.left), Height(result.right)) + 1; return result; }
public AVLTreeNode LR(AVLTreeNode node) { AVLTreeNode result = node.left.right; node.left.right = result.left; result.left = node.left; node.left = result.right; result.right = node; node.height = Math.max(Height(node.left), Height(node.right)) + 1; result.height = Math.max(Height(result.left), Height(result.right)) + 1; return result; }
public AVLTreeNode RL(AVLTreeNode node) { AVLTreeNode result = node.right.left; node.right.left = result.right; result.right = node.right; node.right = result.left; result.left = node; node.height = Math.max(Height(node.left), Height(node.right)) + 1; result.height = Math.max(Height(result.left), Height(result.right)) + 1; return result; }
private AVLTreeNode RR(AVLTreeNode node) { AVLTreeNode result = node.right; node.right = result.left; result.left = node; node.height = Math.max(Height(node.left), Height(node.right)) + 1; result.height = Math.max(Height(result.left), Height(result.right)) + 1; return result; }
|
为了验证最终答案是否正确,除了从 debug 看还写了一个中序遍历的方法来打印数据查看我们最终的答案是否正确:
1 2 3 4 5 6 7 8 9
| public void print(AVLTreeNode node) { if (node == null) { return; } print(node.left); System.out.print(node.val + " "); print(node.right); }
|
我们最终的代码如下:
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137
|
class AVLTree {
AVLTreeNode head;
public AVLTreeNode add(int value) { head = insert(head, value); return head; }
private AVLTreeNode insert(AVLTreeNode root, int val) { if (root == null) { root = new AVLTreeNode(val); root.height = 0; return root; } if (val < root.val) { root.left = insert(root.left, val); } else if (val > root.val) { root.right = insert(root.right, val); } else { root.val = val; } if (Math.abs(Height(root.left) - Height(root.right)) >= 2) { if (Height(root.left) > Height(root.right)) { if (val < root.left.val) { root = LL(root); } else if (val > root.left.val) { root = LR(root); } } else if (Height(root.right) > Height(root.left)) { if (val > root.right.val) { root = RR(root); } else if (val < root.right.val) { root = RL(root); } } } root.height = Math.max(Height(root.left), Height(root.right)) + 1; return root; }
public AVLTreeNode LL(AVLTreeNode node) { AVLTreeNode result = node.left; node.left = result.right; result.right = node; node.height = Math.max(Height(node.left), Height(node.right)) + 1; result.height = Math.max(Height(result.left), Height(result.right)) + 1; return result; }
public AVLTreeNode LR(AVLTreeNode node) { AVLTreeNode result = node.left.right; node.left.right = result.left; result.left = node.left; node.left = result.right; result.right = node; node.height = Math.max(Height(node.left), Height(node.right)) + 1; result.height = Math.max(Height(result.left), Height(result.right)) + 1; return result; }
public AVLTreeNode RL(AVLTreeNode node) { AVLTreeNode result = node.right.left; node.right.left = result.right; result.right = node.right; node.right = result.left; result.left = node; node.height = Math.max(Height(node.left), Height(node.right)) + 1; result.height = Math.max(Height(result.left), Height(result.right)) + 1; return result; }
private AVLTreeNode RR(AVLTreeNode node) { AVLTreeNode result = node.right; node.right = result.left; result.left = node; node.height = Math.max(Height(node.left), Height(node.right)) + 1; result.height = Math.max(Height(result.left), Height(result.right)) + 1; return result; }
public void print(AVLTreeNode node) { if (node == null) { return; } print(node.left); System.out.print(node.val + " "); print(node.right); }
private int Height(AVLTreeNode avlTreeNode) { if (avlTreeNode == null) { return -1; } else { return avlTreeNode.height; } }
}
class AVLTreeNode {
int val; int height = -1; AVLTreeNode left; AVLTreeNode right;
public AVLTreeNode() { }
public AVLTreeNode(int val) { this.val = val; }
}
|
我们写一个 main 方法来检查一下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| public static void main(String[] args) { ListNode head = new ListNode(1); ListNode head1 = new ListNode(2); ListNode head2 = new ListNode(3); ListNode head3 = new ListNode(4); ListNode head4 = new ListNode(5); ListNode head5 = new ListNode(6); head.next = head1; head1.next = head2; head2.next = head3; head3.next = head4; head4.next = head5; AVLTreeNode root = sortedListToBST(head); new AVLTree().print(root); }
public static AVLTreeNode sortedListToBST(ListNode head) { AVLTreeNode root = null; while (head != null) { root = new AVLTree().add(head.val); head = head.next; } return root; }
|
运行代码后发现打印出的信息也是顺序打印的,也没有缺少节点。所以我们就完成了一个平衡二叉树的插入过程。
然后这个题目的解也就自然完成了。