题目来源

今天做了个题：

将一个链表里的数据组装树形结构，链表里的数据已经满足树形结构要求

这道题描述的很简单，但是有很多种情况。他只说了链表数据满足树形结构要求，并没有说明数据到底是什么样的，也就是题目参数具有多样性，这样其实我们给出一种解决方案就可以。而且也只要求将链表转换为树，并没有说是什么树。所以这道题说难也难，说简单也简单。

解题思路

最近也将平衡二叉树的原理看了一下，正好借着这道题将代码手写一下。

我写了一个平衡二叉树的插入方法。我们不管链表里面的数据是如何排序的，我们只要调用树的插入方法即可。在插入方法内部实现树的平衡。

所以我们这道题也就转换成了手写平衡二叉树的插入过程。

代码实现

平衡二叉树

首先我们需要定义平衡二叉树的数据结构，在这里我们就用 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;
		}
		//检查失衡,左右节点的高度差绝对值大于 2 即为失衡
		if (Math.abs(Height(root.left) - Height(root.right)) >= 2) {
			//当左边树高时可能为 LL 型或 LR 型
			if (Height(root.left) > Height(root.right)) {
				//当新插入的值比 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)) {
				//当右边树高时可能为 RR 型或 RL 型
				//当新插入的值比 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;
	}

	/*四种类型转换*/

	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;
}

运行代码后发现打印出的信息也是顺序打印的，也没有缺少节点。所以我们就完成了一个平衡二叉树的插入过程。

然后这个题目的解也就自然完成了。