题目
将一个二叉查找树按照中序遍历转换成双向链表
给定一个二叉查找树：
4
/ \
2 5
/ \
1 3
返回 1<->2<->3<->4<->5。
解题
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
* Definition for Doubly-ListNode.
* public class DoublyListNode {
* int val;
* DoublyListNode next, prev;
* DoublyListNode(int val) {
* this.val = val;
* this.next = this.prev = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of tree
* @return: the head of doubly list node
*/ public DoublyListNode bstToDoublyList(TreeNode root) {
// Write your code here
if(root == null)
return null;
DoublyListNode Root = new DoublyListNode(root.val);
if(root.left==null && root.right==null){
return Root;
}
DoublyListNode left = bstToDoublyList(root.left);
DoublyListNode tmpLeft = left;
while(tmpLeft!=null && tmpLeft.next!=null){
tmpLeft = tmpLeft.next;
}
if(left!=null){
tmpLeft.next = Root;
Root.prev = tmpLeft;
}
DoublyListNode right = bstToDoublyList(root.right);
if(right!=null){
Root.next = right;
right.prev = Root;
}
return left!=null?left:Root;
}
}