first idea come into mind is inorder traversal non-inplace solution:
"""
Definition of TreeNode:
class TreeNode:
def __init__(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
idea: in order traversal
@param root: root of a tree
@return: head node of a doubly linked list
"""
def treeToDoublyList(self, root):
if not root:
return root
res = []
def inorder(node):
if not node:
return
inorder(node.left)
res.append(node)
inorder(node.right)
inorder(root)
for i in range(len(res)-1): # to spare tail for connecting to head
res[i].right = res[i+1]
res[i+1].left = res[i]
res[-1].right = res[0]
res[0].left = res[-1]
return res[0]
in place solution
class Solution:
"""
idea: in order traversal
@param root: root of a tree
@para dummy/head: record first node of the list
@para pre: track previous node from current node
@return: a doubly linked list
"""
def treeToDoublyList(self, root):
# check if tree is empty
if not root:
return root
# create dummy node to save head of the link and prev node to track previous node each recursion
dummy = TreeNode(-1)
self.prev = dummy
def inorder(node,head):
# return when reach to the bottom
if not node:
return
inorder(node.left,head)
# check if head is found
if head == TreeNode(-1):
head = node
else:
#create double link
self.prev.right = node
node.left = self.prev
# prev to save node before each recursion
self.prev = node
inorder(node.right,head)
inorder(root,dummy)
# connect head to tail
self.prev.right = dummy.right
dummy.right.left = self.prev
return dummy.right
in Java Solution 3 with stack
/**
* 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;
* }
* }
*/
public class Solution {
/**
* @param root: root of a tree
* @return: head node of a doubly linked list
*/
public TreeNode treeToDoublyList(TreeNode root) {
if (root == null) return root;
TreeNode pre = null;
TreeNode head = null;
Deque<TreeNode> stack = new ArrayDeque<>();
while (!stack.isEmpty() || root != null){
while(root != null){
stack.push(root);
root = root.left;
}
root = stack.pop();
if(pre == null){
head = root;
}else{
pre.right = root;
root.left = pre;
}
pre = root;
root = root.right;
}
pre.right = head;
head.left = pre;
return head;
}
}