題目來源
今天做了個題：
將一個鏈表里的數(shù)據(jù)組裝樹形結(jié)構(gòu)剩瓶，鏈表里的數(shù)據(jù)已經(jīng)滿足樹形結(jié)構(gòu)要求
這道題描述的很簡單，但是有很多種情況辐脖。他只說了鏈表數(shù)據(jù)滿足樹形結(jié)構(gòu)要求狭莱，并沒有說明數(shù)據(jù)到底是什么樣的僵娃，也就是題目參數(shù)具有多樣性，這樣其實我們給出一種解決方案就可以腋妙。而且也只要求將鏈表轉(zhuǎn)換為樹默怨，并沒有說是什么樹。所以這道題說難也難骤素，說簡單也簡單匙睹。
解題思路
最近也將平衡二叉樹的原理看了一下，正好借著這道題將代碼手寫一下济竹。
我寫了一個平衡二叉樹的插入方法痕檬。我們不管鏈表里面的數(shù)據(jù)是如何排序的，我們只要調(diào)用樹的插入方法即可规辱。在插入方法內(nèi)部實現(xiàn)樹的平衡谆棺。
所以我們這道題也就轉(zhuǎn)換成了手寫平衡二叉樹的插入過程。
代碼實現(xiàn)
平衡二叉樹
首先我們需要定義平衡二叉樹的數(shù)據(jù)結(jié)構(gòu)罕袋，在這里我們就用 int 類型來簡單實現(xiàn)改淑。
/**
* 二叉平衡樹的數(shù)據(jù)類型
*/
class AVLTreeNode {
int val;
int height = -1;
AVLTreeNode left;
AVLTreeNode right;
public AVLTreeNode() {
}
public AVLTreeNode(int val) {
this.val = val;
}
}
接下來我們定義這個平衡二叉樹中所需用到的方法：
class AVLTree {
//定義一個變量，存儲頭部節(jié)點
AVLTreeNode head;
//我們在進行平衡判斷時浴讯，需要知道每個節(jié)點的高度朵夏，從而進行計算
private static int Height(AVLTreeNode avlTreeNode) {
if (avlTreeNode == null) {
return -1;
} else {
return avlTreeNode.height;
}
}
//定義公共方法，實現(xiàn)內(nèi)部封裝
public AVLTreeNode add(int value) {
head = insert(head, value);
return head;
}
//實際插入的方法
private AVLTreeNode insert(AVLTreeNode root, int val) {
...
...
}
}
我們知道榆纽，在平衡二叉樹中仰猖，有四種調(diào)整情況。分別為 LL型奈籽，LR 型饥侵，RL 型，RR 型衣屏。
所以需要將這四個方法提前寫明：
/*四種類型轉(zhuǎn)換*/
public AVLTreeNode LL(AVLTreeNode node) {
//反轉(zhuǎn)結(jié)構(gòu)
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 看還寫了一個中序遍歷的方法來打印數(shù)據(jù)查看我們最終的答案是否正確：
// 中序遍歷
public void print(AVLTreeNode node) {
if (node == null) {
return;
}
print(node.left);
System.out.print(node.val + " ");
print(node.right);
}
我們最終的代碼如下：
/**
* 平衡二叉樹
*/
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) {
//左側(cè)插入
root.left = insert(root.left, val);
} else if (val > root.val) {
//右側(cè)插入
root.right = insert(root.right, val);
} else {
//更新值
root.val = val;
}
//檢查失衡,左右節(jié)點的高度差絕對值大于 2 即為失衡
if (Math.abs(Height(root.left) - Height(root.right)) >= 2) {
//當(dāng)左邊樹高時可能為 LL 型或 LR 型
if (Height(root.left) > Height(root.right)) {
//當(dāng)新插入的值比 root.left 值小時為 LL 型，比 root.left 值大時為 LR 型
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)) {
//當(dāng)右邊樹高時可能為 RR 型或 RL 型
//當(dāng)新插入的值比 root.right 值大時為 RR 型狼忱，比 root.right 值小時為 RL 型
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;
}
/*四種類型轉(zhuǎn)換*/
public AVLTreeNode LL(AVLTreeNode node) {
//反轉(zhuǎn)結(jié)構(gòu)
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;
}
}
}
/**
* 二叉平衡樹的數(shù)據(jù)類型
*/
class AVLTreeNode {
int val;
int height = -1;
AVLTreeNode left;
AVLTreeNode right;
public AVLTreeNode() {
}
public AVLTreeNode(int val) {
this.val = val;
}
}
我們寫一個 main 方法來檢查一下：
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;
}
運行代碼后發(fā)現(xiàn)打印出的信息也是順序打印的膨疏，也沒有缺少節(jié)點。所以我們就完成了一個平衡二叉樹的插入過程钻弄。
然后這個題目的解也就自然完成了佃却。
本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布！
博主郵箱：liunaijie1996@163.com窘俺，有問題可以郵箱交流饲帅。
