This content originally appeared on DEV Community and was authored by Rohith V
Problem Statement
Given the root of a binary tree, flatten the tree into a "linked list":
The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.
Test Cases
Example 1:
Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]
Example 2:
Input: root = []
Output: []
Example 3:
Input: root = [0]
Output: [0]
Constraints:
The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100
Algorithm :
- Here we need to move all our left child nodes to right and append the already present right child node to the end.
- So if we have left child node, first of all store the currently present right child to a variable and keep
root.rightas the left child. Then make the left child as null. - Then the stored right child is appended towards the end of the left child node that is recently attached.
- Do recursion keeping the root node as root.right.
recursion(root.right).
Complexity :
We are going through each of the node so time complexity O(n) and space will be O(H) as we use a recursion stack.
Code :
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public void flatten(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null) {
TreeNode temp = root.right;
root.right = root.left;
root.left = null;
TreeNode current = root.right;
while (current.right != null) {
current = current.right;
}
current.right = temp;
}
flatten(root.right);
}
}
Github :
LeetCode
LeetCode problems that are solved.
This content originally appeared on DEV Community and was authored by Rohith V
Rohith V | Sciencx (2021-11-11T09:06:36+00:00) Leetcode 114. Flatten Binary Tree to Linked List. Retrieved from https://www.scien.cx/2021/11/11/leetcode-114-flatten-binary-tree-to-linked-list/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.