Convert a given Binary Tree to Doubly Linked List | Set 2 | GeeksforGeeks
https://gist.github.com/gcrfelix/3aeb63a919e0eea6e449
The left and right pointers of binary tree nodes should act as previous and next pointers in doubly linked list and the doubly linked list nodes should follow the same order of nodes as in-order traversal of the tree.
题目：Convert Binary Tree to Circular Doubly LinkedList
具体思路是
1. 拿出根节点。
2. 递归处理left， 找到左边最后一个节点，并且连接root到这个节点上。
3. 递归处理right， 找到右边最前面的节点，并且连接root到这个节点上。
4. return。
最后还需要处理一下头连接到尾巴的双向循环。
https://www.techiedelight.com/place-convert-given-binary-tree-to-doubly-linked-list/
X. https://www.jianshu.com/p/f2eac0a35586
X. Not efficient
https://www.hackingnote.com/en/interview/problems/convert-binary-search-tree-to-doubly-linked-list
https://www.ideserve.co.in/learn/convert-a-binary-tree-to-doubly-linked-list
public class ConvertBTtoCircularDoublyLinkedList {
public void solve(TreeNode root) {
if(root == null) {
return;
}
convert(root);
connectHeadAndTail(root);
}
public void convert(TreeNode root) {
if(root == null) {
return;
}
if(root.left != null) {
TreeNode left = root.left;
convert(left);
while(left.right != null) {
left = left.right;
}
left.right = root;
root.left = left;
}
if(root.right != null) {
TreeNode right = root.right;
convert(right);
while(right.left != null) {
right = right.left;
}
right.left = root;
root.right = right;
}
}
public void connectHeadAndTail(TreeNode root) {
TreeNode head = root;
while(head.left != null) {
head = head.left;
}
TreeNode tail = root;
while(tail.right != null) {
tail = tail.right;
}
head.left = tail;
tail.right = head;
}
}
Convert a given Binary Tree to Doubly Linked List | Set 3
The idea is to do inorder traversal of the binary tree. While doing inorder traversal, keep track of the previously visited node in a variable say prev. For every visited node, make it next of prev and previous of this node as prev.
Time Complexity: O(n) where n is the number of nodes in given Binary Tree. The solution simply does two traversals of all Binary Tree nodes.
1) Fix Left Pointers: In this step, we change left pointers to point to previous nodes in DLL. The idea is simple, we do inorder traversal of tree. In inorder traversal, we keep track of previous visited node and change left pointer to the previous node.
2) Fix Right Pointers:
The idea is to use left pointers fixed in step 1. We start from the rightmost node in Binary Tree (BT). The rightmost node is the last node in DLL. Since left pointers are changed to point to previous node in DLL, we can linearly traverse the complete DLL using these pointers. The traversal would be from last to first node. While traversing the DLL, we keep track of the previously visited node and change the right pointer to the previous node.
Convert a given Binary Tree to Doubly Linked List | Set 1
Its not efficient as for every node we go for inorder predecessor and successor!
Time complexity of this code is nLogn.
1. If left subtree exists, process the left subtree
…..1.a) Recursively convert the left subtree to DLL.
…..1.b) Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
…..1.c) Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
…..2.a) Recursively convert the right subtree to DLL.
…..2.b) Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
…..2.c) Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL).
http://www.geeksforgeeks.org/convert-a-given-binary-tree-to-doubly-linked-list-set-4/
For example, below binary tree.
Postorder反而是这些里面最简单的，因为后序的话不需要考虑备份子节点
如果要constant space的话，类似morris遍历的方法，在每次回收节点的时候，回收的是一个链表上的所有节点，我们只需把链表reverse一样，按照要求连接好，然后连接点之前已经构好的list的末尾就可以了。
Flatten Binary Tree to Doubly Linked List As Preorder
这道题是要在flatten to linkedlist的基础上做略微的修改就可以，只要把左指针指向list中前一个node即可.
public class flattenToDoublyLinkedListAsPreorder {
private TreeNode head = null;
private TreeNode tail = null;
public TreeNode flattenRecursively(TreeNode root) {
preOrder(root);
return head;
}
private void preOrder(TreeNode node) {
if (node == null)
return;
TreeNode leftCopy = node.left;
TreeNode rightCopy = node.right;
if(head == null) {
head = node;
head.left = null;
tail = node;
tail.right = null;
} else {
tail.right = node;
node.left = tail;
tail = tail.right;
tail.right = null;
}
preOrder(leftCopy);
preOrder(rightCopy);
}
public TreeNode flattenIteratively(TreeNode root) {
TreeNode curr = root, head = null, tail = null;
Stack<TreeNode> path = new Stack<TreeNode>();
Stack<TreeNode> rightChildren = new Stack<TreeNode>();
while (!path.isEmpty() || curr != null) {
while (curr != null) {
path.push(curr);
rightChildren.push(curr.right);
TreeNode leftCopy = curr.left;
if (head == null) {
head = curr;
tail = curr;
head.left = null;
head.right = null;
} else {
tail.right = curr;
curr.left = tail;
tail = tail.right;
tail.right = null;
}
curr = leftCopy;
}
path.pop();
curr = rightChildren.pop();
}
return head;
}
}
[Algorithm] Flatten Binary Tree to Doubly Linked List As Inorder
在preorder递归和迭代版本做略微修改就行了。迭代版本我们第二次访问节点的时候调整左右指针，注意只要备份右指针，然后去到原右子结点。左子节点不需要备份因为之后我们不会去左子树了。递归版本是类似的，只需备份右子结点
public class flattenToDoublyLinkedListAsInorder {
private TreeNode head = null;
private TreeNode tail = null;
public TreeNode flattenRecursively(TreeNode root) {
InOrder(root);
return head;
}
private void InOrder(TreeNode node) {
if (node == null)
return;
InOrder(node.left);
TreeNode rightCopy = node.right;
if(head == null) {
head = node;
head.left = null;
tail = node;
tail.right = null;
} else {
tail.right = node;
node.left = tail;
tail = tail.right;
tail.right = null;
}
InOrder(rightCopy);
}
public TreeNode flattenIteratively(TreeNode root) {
TreeNode curr = root, head = null, tail = null;
Stack<TreeNode> path = new Stack<TreeNode>();
while (!path.isEmpty() || curr != null) {
while (curr != null) {
path.push(curr);
curr = curr.left;
}
curr = path.pop();
TreeNode rightCopy = curr.right;
if (head == null) {
head = curr;
tail = curr;
head.left = null;
head.right = null;
} else {
tail.right = curr;
curr.left = tail;
tail = tail.right;
tail.right = null;
}
curr = rightCopy;
}
return head;
}
}
Transformation between Binary Tree and Linked Lists
Read full article from Convert a given Binary Tree to Doubly Linked List | Set 2 | GeeksforGeeks
https://gist.github.com/gcrfelix/3aeb63a919e0eea6e449
The left and right pointers of binary tree nodes should act as previous and next pointers in doubly linked list and the doubly linked list nodes should follow the same order of nodes as in-order traversal of the tree.
具体思路是
1. 拿出根节点。
2. 递归处理left， 找到左边最后一个节点，并且连接root到这个节点上。
3. 递归处理right， 找到右边最前面的节点，并且连接root到这个节点上。
4. return。
最后还需要处理一下头连接到尾巴的双向循环。
https://www.techiedelight.com/place-convert-given-binary-tree-to-doubly-linked-list/
X. https://www.jianshu.com/p/f2eac0a35586
In order traverse this tree.
然后每次返回一个数组，第一位放head of sub tree, 第二位放tail of sub tree
然后注意双向链表的连接。
然后每次返回一个数组，第一位放head of sub tree, 第二位放tail of sub tree
然后注意双向链表的连接。
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;
}X. Not efficient
https://www.hackingnote.com/en/interview/problems/convert-binary-search-tree-to-doubly-linked-list
https://www.ideserve.co.in/learn/convert-a-binary-tree-to-doubly-linked-list
public DoublyListNode bstToDoublyList(TreeNode root) {
// Write your code here
if (root == null) return null;
DoublyListNode left = null, right = null;
if (root.left != null) {
left = bstToDoublyList(root.left);
}
DoublyListNode node = new DoublyListNode(root.val);
node.prev = rightMost(left);
if (node.prev != null) {
node.prev.next = node;
}
if (root.right != null) {
right = bstToDoublyList(root.right);
}
node.next = right;
if (node.next != null) {
node.next.prev = node;
}
return leftMost(node);
}
private DoublyListNode leftMost(DoublyListNode node) {
if (node == null) return null;
while (node.prev != null) {
node = node.prev;
}
return node;
}
private DoublyListNode rightMost(DoublyListNode node) {
if (node == null) return null;
while (node.next != null) {
node = node.next;
}
return node;
}
public class ConvertBTtoCircularDoublyLinkedList {
public void solve(TreeNode root) {
if(root == null) {
return;
}
convert(root);
connectHeadAndTail(root);
}
public void convert(TreeNode root) {
if(root == null) {
return;
}
if(root.left != null) {
TreeNode left = root.left;
convert(left);
while(left.right != null) {
left = left.right;
}
left.right = root;
root.left = left;
}
if(root.right != null) {
TreeNode right = root.right;
convert(right);
while(right.left != null) {
right = right.left;
}
right.left = root;
root.right = right;
}
}
public void connectHeadAndTail(TreeNode root) {
TreeNode head = root;
while(head.left != null) {
head = head.left;
}
TreeNode tail = root;
while(tail.right != null) {
tail = tail.right;
}
head.left = tail;
tail.right = head;
}
}
Convert a given Binary Tree to Doubly Linked List | Set 3
The idea is to do inorder traversal of the binary tree. While doing inorder traversal, keep track of the previously visited node in a variable say prev. For every visited node, make it next of prev and previous of this node as prev.
Note that use of static variables like above is not a recommended practice (we have used static for simplicity). Imagine a situation where same function is called for two or more trees, the old value of prev would be used in next call for a different tree. To avoid such problems, we can use double pointer or reference to a pointer.
Time Complexity: The above program does a simple inorder traversal, so time complexity is O(n) where n is the number of nodes in given binary tree.
Convert a given Binary Tree to Doubly Linked List | Set 2Time Complexity: O(n) where n is the number of nodes in given Binary Tree. The solution simply does two traversals of all Binary Tree nodes.
1) Fix Left Pointers: In this step, we change left pointers to point to previous nodes in DLL. The idea is simple, we do inorder traversal of tree. In inorder traversal, we keep track of previous visited node and change left pointer to the previous node.
2) Fix Right Pointers:
The idea is to use left pointers fixed in step 1. We start from the rightmost node in Binary Tree (BT). The rightmost node is the last node in DLL. Since left pointers are changed to point to previous node in DLL, we can linearly traverse the complete DLL using these pointers. The traversal would be from last to first node. While traversing the DLL, we keep track of the previously visited node and change the right pointer to the previous node.
// Changes left pointers to work as previous pointers in converted DLL// The function simply does inorder traversal of Binary Tree and updates// left pointer using previously visited nodevoid fixPrevPtr(struct node *root){ static struct node *pre = NULL; if (root != NULL) { fixPrevPtr(root->left); root->left = pre; pre = root; fixPrevPtr(root->right); }}// Changes right pointers to work as next pointers in converted DLLstruct node *fixNextPtr(struct node *root){ struct node *prev = NULL; // Find the right most node in BT or last node in DLL while (root && root->right != NULL) root = root->right; // Start from the rightmost node, traverse back using left pointers. // While traversing, change right pointer of nodes. while (root && root->left != NULL) { prev = root; root = root->left; root->right = prev; } // The leftmost node is head of linked list, return it return (root);}// The main function that converts BST to DLL and returns head of DLLstruct node *BTToDLL(struct node *root){ // Set the previous pointer fixPrevPtr(root); // Set the next pointer and return head of DLL return fixNextPtr(root);}Its not efficient as for every node we go for inorder predecessor and successor!
Time complexity of this code is nLogn.
1. If left subtree exists, process the left subtree
…..1.a) Recursively convert the left subtree to DLL.
…..1.b) Then find inorder predecessor of root in left subtree (inorder predecessor is rightmost node in left subtree).
…..1.c) Make inorder predecessor as previous of root and root as next of inorder predecessor.
2. If right subtree exists, process the right subtree (Below 3 steps are similar to left subtree).
…..2.a) Recursively convert the right subtree to DLL.
…..2.b) Then find inorder successor of root in right subtree (inorder successor is leftmost node in right subtree).
…..2.c) Make inorder successor as next of root and root as previous of inorder successor.
3. Find the leftmost node and return it (the leftmost node is always head of converted DLL).
/* This is the core function to convert Tree to list. This function follows steps 1 and 2 of the above algorithm */node* bintree2listUtil(node* root){ // Base case if (root == NULL) return root; // Convert the left subtree and link to root if (root->left != NULL) { // Convert the left subtree node* left = bintree2listUtil(root->left); // Find inorder predecessor. After this loop, left // will point to the inorder predecessor for (; left->right!=NULL; left=left->right); // Make root as next of the predecessor left->right = root; // Make predecssor as previous of root root->left = left; } // Convert the right subtree and link to root if (root->right!=NULL) { // Convert the right subtree node* right = bintree2listUtil(root->right); // Find inorder successor. After this loop, right // will point to the inorder successor for (; right->left!=NULL; right = right->left); // Make root as previous of successor right->left = root; // Make successor as next of root root->right = right; } return root;}// The main function that first calls bintree2listUtil(), then follows step 3 // of the above algorithmnode* bintree2list(node *root){ // Base case if (root == NULL) return root; // Convert to DLL using bintree2listUtil() root = bintree2listUtil(root); // bintree2listUtil() returns root node of the converted // DLL. We need pointer to the leftmost node which is // head of the constructed DLL, so move to the leftmost node while (root->left != NULL) root = root->left; return (root);}
In the following implementation, we traverse the tree in inorder fashion. We add nodes at the beginning of current linked list and update head of the list using pointer to head pointer. Since we insert at the beginning, we need to process leaves in reverse order. For reverse order, we first traverse the right subtree before the left subtree. i.e. do a reverse inorder traversal.
http://fisherlei.blogspot.com/2012/12/leetcode-flatten-binary-tree-to-linked.htmlFor example, below binary tree.
If we flatten it with in-order, the process should like below. And here I use the left pointer of head node to track the tail node.
1: TreeNode* flatten(TreeNode *root) {
2: if (root == NULL) return NULL;
3: TreeNode* rightTree = root->right;
4: TreeNode* newHead = root;
5: TreeNode* leftList = flatten(root->left);
6: if (leftList != NULL)
7: {
8: newHead = leftList;
9: TreeNode* tail = leftList->left;
10: tail->right = root;
11: root->left = tail;
12: leftList->left = root;
13: }
14: TreeNode* rightList = flatten(rightTree);
15: if (rightList != NULL)
16: {
17: root->right = rightList;
18: newHead->left = rightList->left;
19: rightList->left = root;
20: }
21: return newHead;
22: } Postorder反而是这些里面最简单的，因为后序的话不需要考虑备份子节点
如果要constant space的话，类似morris遍历的方法，在每次回收节点的时候，回收的是一个链表上的所有节点，我们只需把链表reverse一样，按照要求连接好，然后连接点之前已经构好的list的末尾就可以了。
public class flattenToDoublyLinkedListAsPostorder {
private TreeNode head = null;
private TreeNode tail = null;
public TreeNode flattenRecursively(TreeNode root) {
postOrder(root);
return head;
}
private void postOrder(TreeNode node) {
if (node == null)
return;
postOrder(node.left);
postOrder(node.right);
if(head == null) {
head = node;
head.left = null;
tail = node;
tail.right = null;
} else {
tail.right = node;
node.left = tail;
tail = tail.right;
tail.right = null;
}
}
public TreeNode flattenIteratively(TreeNode root) {
if (root == null)
return null;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode pre = null, head = null, tail = null;
stack.push(root);
while(!stack.isEmpty()) {
TreeNode curr = stack.peek();
if (isLeaf(curr) || (pre != null && (pre == curr.left || pre == curr.right))) {
stack.pop();
if (head == null) {
head = curr;
tail = curr;
head.left = null;
head.right = null;
} else {
tail.right = curr;
curr.left = tail;
tail = tail.right;
tail.right = null;
}
pre = curr;
}
else {
if (curr.right != null)
stack.push(curr.right);
if (curr.left != null)
stack.push(curr.left);
}
}
return head;
}
}
这道题是要在flatten to linkedlist的基础上做略微的修改就可以，只要把左指针指向list中前一个node即可.
public class flattenToDoublyLinkedListAsPreorder {
private TreeNode head = null;
private TreeNode tail = null;
public TreeNode flattenRecursively(TreeNode root) {
preOrder(root);
return head;
}
private void preOrder(TreeNode node) {
if (node == null)
return;
TreeNode leftCopy = node.left;
TreeNode rightCopy = node.right;
if(head == null) {
head = node;
head.left = null;
tail = node;
tail.right = null;
} else {
tail.right = node;
node.left = tail;
tail = tail.right;
tail.right = null;
}
preOrder(leftCopy);
preOrder(rightCopy);
}
public TreeNode flattenIteratively(TreeNode root) {
TreeNode curr = root, head = null, tail = null;
Stack<TreeNode> path = new Stack<TreeNode>();
Stack<TreeNode> rightChildren = new Stack<TreeNode>();
while (!path.isEmpty() || curr != null) {
while (curr != null) {
path.push(curr);
rightChildren.push(curr.right);
TreeNode leftCopy = curr.left;
if (head == null) {
head = curr;
tail = curr;
head.left = null;
head.right = null;
} else {
tail.right = curr;
curr.left = tail;
tail = tail.right;
tail.right = null;
}
curr = leftCopy;
}
path.pop();
curr = rightChildren.pop();
}
return head;
}
}
[Algorithm] Flatten Binary Tree to Doubly Linked List As Inorder
在preorder递归和迭代版本做略微修改就行了。迭代版本我们第二次访问节点的时候调整左右指针，注意只要备份右指针，然后去到原右子结点。左子节点不需要备份因为之后我们不会去左子树了。递归版本是类似的，只需备份右子结点
public class flattenToDoublyLinkedListAsInorder {
private TreeNode head = null;
private TreeNode tail = null;
public TreeNode flattenRecursively(TreeNode root) {
InOrder(root);
return head;
}
private void InOrder(TreeNode node) {
if (node == null)
return;
InOrder(node.left);
TreeNode rightCopy = node.right;
if(head == null) {
head = node;
head.left = null;
tail = node;
tail.right = null;
} else {
tail.right = node;
node.left = tail;
tail = tail.right;
tail.right = null;
}
InOrder(rightCopy);
}
public TreeNode flattenIteratively(TreeNode root) {
TreeNode curr = root, head = null, tail = null;
Stack<TreeNode> path = new Stack<TreeNode>();
while (!path.isEmpty() || curr != null) {
while (curr != null) {
path.push(curr);
curr = curr.left;
}
curr = path.pop();
TreeNode rightCopy = curr.right;
if (head == null) {
head = curr;
tail = curr;
head.left = null;
head.right = null;
} else {
tail.right = curr;
curr.left = tail;
tail = tail.right;
tail.right = null;
}
curr = rightCopy;
}
return head;
}
}
Transformation between Binary Tree and Linked Lists
Read full article from Convert a given Binary Tree to Doubly Linked List | Set 2 | GeeksforGeeks
