树的头指针

数据结构看完对链表头指针印象还是很深刻的，但是没有实践写过相关代码，近期leetcode刷题碰到用数据结构的中等题都歇菜了，今天是897递增顺序搜索树一个简单题，看完后有了思路，中序遍历（递归）+右子树斜树，但是写代码就犯难了，我发现我还没用java写过数据结构，之前看的大话数据结构还是用C写的，然后我便参考了宫水三叶的题解。

1
2
3
4
5
6
7
8
9
TreeNode dummy = new TreeNode(-1);//头指针，方便头结点找前驱结点
TreeNode head = dummy;//把头指针给头结点
for (TreeNode node : list) {
    head.right = node;//遍历排好的中序遍历list,全部给头结点的右子树
    node.left = null;//左子树为空
    head = node;//把右子树设为新的头结点
}
return dummy.right;//头指针并不需要，只是为了头结点服务，所以直接返回其右子树即头结点树

题解里这段把我看懵了，不知道为什么要新建dummy这个节点，返回值为什么是dummy.right。在网上搜了一会儿，我找到了答案。

dummy就是一个头指针，因为头结点没有前驱节点，dummy相当于一个工具服务头结点，用来定义头结点的。然后把dummy赋予head，开始循环赋值，最后返回值自然而然便是dummy.right，因为dummy头指针没用，从其右子树开始。

果然还是实践出真知，以后初始化树，头指针的应用我是记下了。