378. Convert Binary Tree to DoublyLinkedList

Leave a comment

September 17, 2016 by oneOokay

要求把一个binary tree按照in-order的顺序转换成一个doublylinkedlist

对binary tree做in-order traversal:helper method:

  1. 第一步:判断node是否为null,if true,return
  2. 第二步:helper(node.left);
  3. 第三步:对该node进行操作 :
    • 如果这个是加入dll的第一个node,那么把它作为head。
    • 把当前的node与这个new node连起来。
  4. 第四步:helper(node.right)。

private DoublyListNode headNode = null;
private DoublyListNode dummy = null;
public DoublyListNode bstToDoublyList(TreeNode root) {
if (root == null) {
return null;
}
helper(root);
return headNode;
}
//in-order traversal
private void helper(TreeNode node){
if (node == null) {
return;
}
helper(node.left); //left first : in-order
if (headNode == null) { //如果是第一个node,把它赋给headNode
headNode = new DoublyListNode(node.val);
dummy = headNode;//dummy node开始traversal
}else {
DoublyListNode newNode = new DoublyListNode(node.val);
dummy.next = newNode;
newNode.prev = dummy;
dummy = newNode;
}
helper(node.right);
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: