二叉搜索树与双向链表
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。
为了让您更好地理解问题,以下面的二叉搜索树为例:
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
思路: 可以将整颗树的转化分解为左子树转化和右子树转化. 然后对于左子树转化后的结果获取头尾节点更新与当前根节点的指针即可, 右子树同样如此
代码:
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
|
class Solution { public Node treeToDoublyList(Node root) { if(root == null) { return null; } Node ret = root; Node end = root; Node left = root.left; Node right = root.right; Node linkLeft = treeToDoublyList(left); Node linkRight = treeToDoublyList(right); if(linkLeft != null) { ret = linkLeft; Node tmp = linkLeft; while(tmp.right != null) { if(tmp.right == linkLeft){ break; } tmp = tmp.right; } tmp.right = root; root.left = tmp; } if(linkRight != null) { Node tmp = linkRight; while(tmp.right != null) { if(tmp.right == linkRight){ break; } tmp = tmp.right; } root.right = linkRight; linkRight.left = root; tmp.right = ret; ret.left = tmp; } else { ret.left = root; root.right = ret; } return ret; } }
|