Binary Tree to Doubly Linked List

Given the root of a binary tree, convert it into a doubly linked list in inorder order. Return the values of the list from head to tail. Pattern focus: Inorder DFS (Left Root Right). The inorder sequence becomes the linked list order.

Input Format

root = binary tree root

Output Format

values in the doubly linked list from head to tail

Constraints

  • 1 <= number of nodes <= 10^5
  • -10^4 <= node values <= 10^4
  • Input must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

root = [4,2,5,1,3]

Output:

[1,2,3,4,5]

Explanation:

Inorder traversal of the tree is 1, 2, 3, 4, 5.

Example 2:

Input:

root = [2,1,3]

Output:

[1,2,3]

Explanation:

The doubly linked list follows inorder order.

Loading...
Binary Tree to Doubly Linked List - Binary Tree