树的头指针

    数据结构看完对链表头指针印象还是很深刻的,但是没有实践写过相关代码,近期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头指针没用,从其右子树开始。

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