这不是一个Leetcode 题目.我自己写了下。
题意如下:
Convert a binary search tree to a sorted, circular, doubly-linked list, in place (using the tree nodes as the new list nodes).
use leftChild as "prev"
use rightChild as "next
My code:
import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
public TreeNode traverse(TreeNode root) {
if (root == null)
return null;
return dfs(root)[0];
}
private TreeNode[] dfs(TreeNode root) {
if (root == null)
return null;
TreeNode[] left = dfs(root.left);
TreeNode head = null;
TreeNode tail = null;
if (left != null) {
head = left[0];
left[1].right = root;
root.left = left[1];
}
TreeNode[] right = dfs(root.right);
if (right != null) {
root.right = right[0];
right[0].left = root;
tail = right[1];
}
TreeNode[] ret = new TreeNode[2];
ret[0] = (head == null ? root : head);
ret[1] = (tail == null ? root : tail);
return ret;
}
public static void main(String[] args) {
Solution test = new Solution();
TreeNode a1 = new TreeNode(1);
TreeNode a2 = new TreeNode(2);
TreeNode a3 = new TreeNode(3);
TreeNode a4 = new TreeNode(4);
TreeNode a5 = new TreeNode(5);
TreeNode a6 = new TreeNode(6);
TreeNode a7 = new TreeNode(7);
a1.left = a2;
a1.right = a3;
a2.left = a4;
a2.right = a5;
a3.left = a6;
a3.right = a7;
TreeNode head = test.traverse(a1);
TreeNode tail = null;
while (head.right != null) {
System.out.println(head.val);
head = head.right;
}
System.out.println(head.val);
tail = head;
System.out.println("**************");
while (tail != null) {
System.out.println(tail.val);
tail = tail.left;
}
}
}
自己测试了下。感觉差不多了。其实就是一个简单的dfs,in order traverse this tree.
然后每次返回一个数组,第一位放head of sub tree, 第二位放tail of sub tree
然后注意双向链表的连接。
Anyway, Good luck, Richardo!