Leetcode Solutions (161 Part Series)
1 Solution: Next Permutation
2 Solution: Trim a Binary Search Tree
… 157 more parts…
3 Leetcode Solutions Index
4 Solution: Minimize Deviation in Array
5 Solution: Vertical Order Traversal of a Binary Tree
6 Solution: Count Ways to Make Array With Product
7 Solution: Smallest String With A Given Numeric Value
8 Solution: Linked List Cycle
9 Solution: Path With Minimum Effort
10 Solution: Concatenation of Consecutive Binary Numbers
11 Solution: Minimum Operations to Make a Subsequence
12 Solution: Longest Harmonious Subsequence
13 Solution: Simplify Path
14 Solution: Building Boxes
15 Solution: Decode XORed Permutation
16 Solution: Binary Tree Right Side View
17 Solution: Find Kth Largest XOR Coordinate Value
18 Solution: Change Minimum Characters to Satisfy One of Three Conditions
19 Solution: Shortest Distance to a Character
20 Solution: Peeking Iterator
21 Solution: Convert BST to Greater Tree
22 Solution: Copy List with Random Pointer
23 Solution: Valid Anagram
24 Solution: Number of Steps to Reduce a Number to Zero
25 Solution: Shortest Path in Binary Matrix
26 Solution: Is Graph Bipartite?
27 Solution: Maximum Score From Removing Substrings (ver. 1)
28 Solution: Maximum Score From Removing Substrings (ver. 2)
29 Solution: Sort the Matrix Diagonally
30 Solution: The K Weakest Rows in a Matrix (ver. 1)
31 Solution: The K Weakest Rows in a Matrix (ver. 2)
32 Solution: Letter Case Permutation
33 Solution: Container With Most Water
34 Solution: Arithmetic Slices
35 Solution: Minimum Remove to Make Valid Parentheses
36 Solution: Roman to Integer
37 Solution: Broken Calculator
38 Solution: Find the Most Competitive Subsequence
39 Solution: Longest Word in Dictionary through Deleting
40 Solution: Search a 2D Matrix II
41 Solution: Score of Parentheses
42 Solution: Shortest Unsorted Continuous Subarray
43 Solution: Validate Stack Sequences
44 Solution: Divide Two Integers (ver. 1)
45 Solution: Divide Two Integers (ver. 2)
46 Solution: Maximum Frequency Stack
47 Solution: Distribute Candies
48 Solution: Set Mismatch (ver. 1)
49 Solution: Set Mismatch (ver. 2)
50 Solution: Missing Number
51 Solution: Intersection of Two Linked Lists
52 Solution: Average of Levels in Binary Tree
53 Solution: Short Encoding of Words (ver. 1)
54 Solution: Design HashMap (ver. 1)
55 Solution: Short Encoding of Words (ver. 2)
56 Solution: Design HashMap (ver. 2)
57 Solution: Remove Palindromic Subsequences
58 Solution: Add One Row to Tree
59 Solution: Integer to Roman
60 Solution: Coin Change
61 Solution: Check If a String Contains All Binary Codes of Size K
62 Solution: Binary Trees With Factors
63 Solution: Swapping Nodes in a Linked List
64 Solution: Encode and Decode TinyURL
65 Solution: Best Time to Buy and Sell Stock with Transaction Fee
66 Solution: Generate Random Point in a Circle
67 Solution: Wiggle Subsequence
68 Solution: Keys and Rooms
69 Solution: Design Underground System
70 Solution: Reordered Power of 2
71 Solution: Vowel Spellchecker
72 Solution: 3Sum With Multiplicity
73 Solution: Advantage Shuffle
74 Solution: Pacific Atlantic Water Flow
75 Solution: Word Subsets
76 Solution: Palindromic Substrings
77 Solution: Reconstruct Original Digits from English
78 Solution: Flip Binary Tree To Match Preorder Traversal
79 Solution: Russian Doll Envelopes
80 Solution: Stamping The Sequence
81 Solution: Palindrome Linked List
82 Solution: Ones and Zeroes
83 Solution: Longest Valid Parentheses
84 Solution: Design Circular Queue
85 Solution: Global and Local Inversions
86 Solution: Minimum Operations to Make Array Equal
87 Solution: Determine if String Halves Are Alike
88 Solution: Letter Combinations of a Phone Number
89 Solution: Verifying an Alien Dictionary
90 Solution: Longest Increasing Path in a Matrix
91 Solution: Deepest Leaves Sum
92 Solution: Beautiful Arrangement II
93 Solution: Flatten Nested List Iterator
94 Solution: Partition List
95 Solution: Fibonacci Number
96 Solution: Remove All Adjacent Duplicates in String II
97 Solution: Number of Submatrices That Sum to Target
98 Solution: Remove Nth Node From End of List
99 Solution: Combination Sum IV
100 Solution: N-ary Tree Preorder Traversal
101 Solution: Triangle
102 Solution: Brick Wall
103 Solution: Count Binary Substrings
104 Solution: Critical Connections in a Network
105 Solution: Rotate Image
106 Solution: Furthest Building You Can Reach
107 Solution: Power of Three
108 Solution: Unique Paths II
109 Solution: Find First and Last Position of Element in Sorted Array
110 Solution: Powerful Integers
111 Solution: Prefix and Suffix Search
112 Solution: Course Schedule III
113 Solution: Running Sum of 1d Array
114 Solution: Non-decreasing Array
115 Solution: Jump Game II
116 Solution: Convert Sorted List to Binary Search Tree
117 Solution: Delete Operation for Two Strings
118 Solution: Super Palindromes
119 Solution: Construct Target Array With Multiple Sums
120 Solution: Count Primes
121 Solution: Maximum Points You Can Obtain from Cards
122 Solution: Range Sum Query 2D – Immutable
123 Solution: Ambiguous Coordinates
124 Solution: Flatten Binary Tree to Linked List
125 Solution: Valid Number
126 Solution: Binary Tree Cameras
127 Solution: Longest String Chain
128 Solution: Find Duplicate File in System
129 Solution: Minimum Moves to Equal Array Elements II
130 Solution: Binary Tree Level Order Traversal
131 Solution: Find and Replace Pattern
132 Solution: N-Queens
133 Solution: To Lower Case
134 Solution: Evaluate Reverse Polish Notation
135 Solution: Partitioning Into Minimum Number Of Deci-Binary Numbers
136 Solution: Maximum Product of Word Lengths
137 Solution: Maximum Erasure Value
138 Solution: N-Queens II
139 Solution: Maximum Gap
140 Solution: Search Suggestions System
141 Solution: Max Area of Island
142 Solution: Interleaving String
143 Solution: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
144 Solution: Open the Lock
145 Solution: Maximum Performance of a Team
146 Solution: Longest Consecutive Sequence
147 Solution: Min Cost Climbing Stairs
148 Solution: Construct Binary Tree from Preorder and Inorder Traversal
149 Solution: Jump Game VI
150 Solution: My Calendar I
151 Solution: Stone Game VII
152 Solution: Minimum Number of Refueling Stops
153 Solution: Palindrome Pairs
154 Solution: Maximum Units on a Truck
155 Solution: Matchsticks to Square
156 Solution: Generate Parentheses
157 Solution: Number of Subarrays with Bounded Maximum
158 Solution: Swim in Rising Water
159 Solution: Pascal’s Triangle
160 Solution: Out of Boundary Paths
161 Solution: Redundant Connection
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode’s forums.
Leetcode Problem #114 (Medium): Flatten Binary Tree to Linked List
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
Given the
rootof a binary tree, flatten the tree into a “linked list”:
- The “linked list” should use the same
TreeNodeclass where therightchild pointer points to the next node in the list and theleftchild pointer is alwaysnull.- The “linked list” should be in the same order as a pre-order traversal of the binary tree.
Examples:
Example 1: Input: root = [1,2,5,3,4,null,6] Output: [1,null,2,null,3,null,4,null,5,null,6] Visual:
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
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
Morris Traversal (O(1) Space, O(N) Time) Approach:
There is actually a way to traverse a binary tree with a space complexity of O(1) while staying at a time complexity of O(N), though it does require modifying the tree’s structure. In this problem that’s specifically being called for, so it’s a valid approach, though it won’t always be appropriate to modify the source binary tree in other situations.
The approach is called the Morris traversal. At its heart, it takes advantage of the basic nature of ordered traversals to iterate through and unwind the tree. In a pre-order traversal of a binary tree, each vertex is processed in (node, left, right) order. This means that the entire left subtree could be placed between the node and its right subtree.
To do this, however, we’ll first have to locate the last node in the left subtree. This is easy enough, since we know that the last node of a pre-order tree can be found by moving right as many times as possible from its root.
So we should be able to move through the binary tree, keeping track of the curent node (curr). Whenever we find a left subtree, we can dispatch a runner to find its last node, then stitch together both ends of the left subtree into the right path of curr, taking heed to sever the left connection at curr.
Once that’s done, we can continue to move curr to the right, looking for the next left subtree. When curr can no longer move right, the tree will be successfully flattened.
- Time Complexity: O(N) where N is the number of nodes in the binary tree
- Space Complexity: O(1)
O(1) Space Approach:
In order to properly connect the linked list, we’ll need to start at the bottom and work up. This means that we’ll need to move in reverse pre-order traversal order through the binary tree. Since pre-order traversal is normally (node, left, right), we’ll have to move in the reverse order of (right, left, node).
In order to complete this solution in O(1) space, we won’t be able to conveniently backtrack via a stack, so the key to this solution will be to retreat all the way back up to the root each time we reach a leaf. This will push the time complexity to O(N^2).
We’ll want to first set up head and curr to keep track of the head of the linked list we’re building and the current node we’re visiting. We’ll know we’re finished once head = root.
To follow the reverse pre-order traversal order, we’ll first attempt to go right and then left. Since we’re backtracking to root, however, we’ll eventually run back into the same node that we’ve set as head doing this. To prevent this, we’ll stop before moving to the head node and sever the connection.
Now that we can’t run into already-completed territory, we can be confident that any leaf we move to must be the next value for head, so we should connect it to the old head, update head, and reset back to the root.
As noted before, once head = root, we’ve finished our traversal and can exit the function.
- Time Complexity: O(N^2) where N is the number of nodes in the binary tree, due to repeated backtracking to root
- Space Complexity: O(1)
Recursive Approach:
In order to properly connect the linked list, we’ll need to start at the bottom and work up. This means that we’ll need to move in reverse pre-order traversal order through the binary tree. Since pre-order traversal is normally (node, left, right), we’ll have to move in the reverse order of (right, left, node).
Binary tree traversal is prime ground for a recursive solution, so let’s define a helper (revPreOrder) for the purpose. We’ll also keep a global variable head to keep track of the head of the linked list as we work our way backwards.
Per our reverse pre-order traversal approach, we want to recursively work down the right path first then the left path, if they exist. Once we’ve flattened the left and right paths recursively, head should at this point be equal to the next node after the current one, so we should set it as node.right. We shouldn’t forget to set node.left to null, as well.
Once we’re done with the current node, we can update head to node and allow the recursion to complete and move back up to the next layer. Once the recursion stack is exhausted, head will be equal to root again.
Lastly, we have to deal with an edge case of an empty root, so we can just make sure to only call the initial recursion on root if root actually is a node. There is no need for a return statement, because the test suite will evaluate root directly.
- Time Complexity: O(N) where N is the number of nodes in the binary tree
- Space Complexity: O(N) for the recursion stack, which is as long as the maximum depth of the binary tree, which can go up to N
Javascript Code:
(Jump to: Problem Description || Solution Idea)
w/ Morris Traversal:
var flatten = function(root) {
let curr = root
while (curr) {
if (curr.left) {
let runner = curr.left
while (runner.right) runner = runner.right
runner.right = curr.right, curr.right = curr.left, curr.left = null
}
curr = curr.right
}
};
Enter fullscreen mode Exit fullscreen mode
w/ O(1) Space:
var flatten = function(root) {
let head = null, curr = root
while (head != root) {
if (curr.right === head) curr.right = null
if (curr.left === head) curr.left = null
if (curr.right) curr = curr.right
else if (curr.left) curr = curr.left
else curr.right = head, head = curr, curr = root
}
};
Enter fullscreen mode Exit fullscreen mode
w/ Recursion:
var flatten = function(root) {
let head = null
const revPreOrder = node => {
if (node.right) revPreOrder(node.right)
if (node.left) revPreOrder(node.left)
node.left = null, node.right = head, head = node
}
if (root) revPreOrder(root)
};
Enter fullscreen mode Exit fullscreen mode
Python Code:
(Jump to: Problem Description || Solution Idea)
w/ Morris Traversal:
class Solution:
def flatten(self, root: TreeNode) -> None:
curr = root
while curr:
if curr.left:
runner = curr.left
while runner.right: runner = runner.right
runner.right, curr.right, curr.left = curr.right, curr.left, None
curr = curr.right
Enter fullscreen mode Exit fullscreen mode
w/ O(1) Space:
class Solution:
def flatten(self, root: TreeNode) -> None:
head, curr = None, root
while head != root:
if curr.right == head: curr.right = None
if curr.left == head: curr.left = None
if curr.right: curr = curr.right
elif curr.left: curr = curr.left
else: curr.right, head, curr = head, curr, root
Enter fullscreen mode Exit fullscreen mode
w/ Recursion:
class Solution:
head = None
def flatten(self, root: TreeNode) -> None:
def revPreOrder(node: TreeNode) -> None:
if node.right: revPreOrder(node.right)
if node.left: revPreOrder(node.left)
node.left, node.right, self.head = None, self.head, node
if root: revPreOrder(root)
Enter fullscreen mode Exit fullscreen mode
Java Code:
(Jump to: Problem Description || Solution Idea)
w/ Morris Traversal:
class Solution {
public void flatten(TreeNode root) {
TreeNode curr = root;
while (curr != null) {
if (curr.left != null) {
TreeNode runner = curr.left;
while (runner.right != null) runner = runner.right;
runner.right = curr.right;
curr.right = curr.left;
curr.left = null;
}
curr = curr.right;
}
}
}
Enter fullscreen mode Exit fullscreen mode
w/ O(1) Space:
class Solution {
public void flatten(TreeNode root) {
TreeNode head = null, curr = root;
while (head != root) {
if (curr.right == head) curr.right = null;
if (curr.left == head) curr.left = null;
if (curr.right != null) curr = curr.right;
else if (curr.left != null) curr = curr.left;
else {
curr.right = head;
head = curr;
curr = root;
}
}
}
}
Enter fullscreen mode Exit fullscreen mode
w/ Recursion:
class Solution {
TreeNode head = null;
public void flatten(TreeNode root) {
if (root != null) revPreOrder(root);
}
private void revPreOrder(TreeNode node) {
if (node.right != null) revPreOrder(node.right);
if (node.left != null) revPreOrder(node.left);
node.left = null;
node.right = head;
head = node;
}
}
Enter fullscreen mode Exit fullscreen mode
C++ Code:
(Jump to: Problem Description || Solution Idea)
w/ Morris Traversal:
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode* curr = root;
while (curr) {
if (curr->left) {
TreeNode* runner = curr->left;
while (runner->right != nullptr) runner = runner->right;
runner->right = curr->right, curr->right = curr->left, curr->left = nullptr;
}
curr = curr->right;
}
}
};
Enter fullscreen mode Exit fullscreen mode
w/ O(1) Space:
class Solution {
public:
void flatten(TreeNode* root) {
TreeNode *head = nullptr, *curr = root;
while (head != root) {
if (curr->right == head) curr->right = nullptr;
if (curr->left == head) curr->left = nullptr;
if (curr->right) curr = curr->right;
else if (curr->left) curr = curr->left;
else curr->right = head, head = curr, curr = root;
}
}
};
Enter fullscreen mode Exit fullscreen mode
w/ Recursion:
class Solution {
public:
void flatten(TreeNode* root) {
if (root) revPreOrder(root);
}
private:
TreeNode* head = nullptr;
void revPreOrder(TreeNode* node) {
if (node->right) revPreOrder(node->right);
if (node->left) revPreOrder(node->left);
node->left = nullptr, node->right = head, head = node;
}
};
Enter fullscreen mode Exit fullscreen mode
Leetcode Solutions (161 Part Series)
1 Solution: Next Permutation
2 Solution: Trim a Binary Search Tree
… 157 more parts…
3 Leetcode Solutions Index
4 Solution: Minimize Deviation in Array
5 Solution: Vertical Order Traversal of a Binary Tree
6 Solution: Count Ways to Make Array With Product
7 Solution: Smallest String With A Given Numeric Value
8 Solution: Linked List Cycle
9 Solution: Path With Minimum Effort
10 Solution: Concatenation of Consecutive Binary Numbers
11 Solution: Minimum Operations to Make a Subsequence
12 Solution: Longest Harmonious Subsequence
13 Solution: Simplify Path
14 Solution: Building Boxes
15 Solution: Decode XORed Permutation
16 Solution: Binary Tree Right Side View
17 Solution: Find Kth Largest XOR Coordinate Value
18 Solution: Change Minimum Characters to Satisfy One of Three Conditions
19 Solution: Shortest Distance to a Character
20 Solution: Peeking Iterator
21 Solution: Convert BST to Greater Tree
22 Solution: Copy List with Random Pointer
23 Solution: Valid Anagram
24 Solution: Number of Steps to Reduce a Number to Zero
25 Solution: Shortest Path in Binary Matrix
26 Solution: Is Graph Bipartite?
27 Solution: Maximum Score From Removing Substrings (ver. 1)
28 Solution: Maximum Score From Removing Substrings (ver. 2)
29 Solution: Sort the Matrix Diagonally
30 Solution: The K Weakest Rows in a Matrix (ver. 1)
31 Solution: The K Weakest Rows in a Matrix (ver. 2)
32 Solution: Letter Case Permutation
33 Solution: Container With Most Water
34 Solution: Arithmetic Slices
35 Solution: Minimum Remove to Make Valid Parentheses
36 Solution: Roman to Integer
37 Solution: Broken Calculator
38 Solution: Find the Most Competitive Subsequence
39 Solution: Longest Word in Dictionary through Deleting
40 Solution: Search a 2D Matrix II
41 Solution: Score of Parentheses
42 Solution: Shortest Unsorted Continuous Subarray
43 Solution: Validate Stack Sequences
44 Solution: Divide Two Integers (ver. 1)
45 Solution: Divide Two Integers (ver. 2)
46 Solution: Maximum Frequency Stack
47 Solution: Distribute Candies
48 Solution: Set Mismatch (ver. 1)
49 Solution: Set Mismatch (ver. 2)
50 Solution: Missing Number
51 Solution: Intersection of Two Linked Lists
52 Solution: Average of Levels in Binary Tree
53 Solution: Short Encoding of Words (ver. 1)
54 Solution: Design HashMap (ver. 1)
55 Solution: Short Encoding of Words (ver. 2)
56 Solution: Design HashMap (ver. 2)
57 Solution: Remove Palindromic Subsequences
58 Solution: Add One Row to Tree
59 Solution: Integer to Roman
60 Solution: Coin Change
61 Solution: Check If a String Contains All Binary Codes of Size K
62 Solution: Binary Trees With Factors
63 Solution: Swapping Nodes in a Linked List
64 Solution: Encode and Decode TinyURL
65 Solution: Best Time to Buy and Sell Stock with Transaction Fee
66 Solution: Generate Random Point in a Circle
67 Solution: Wiggle Subsequence
68 Solution: Keys and Rooms
69 Solution: Design Underground System
70 Solution: Reordered Power of 2
71 Solution: Vowel Spellchecker
72 Solution: 3Sum With Multiplicity
73 Solution: Advantage Shuffle
74 Solution: Pacific Atlantic Water Flow
75 Solution: Word Subsets
76 Solution: Palindromic Substrings
77 Solution: Reconstruct Original Digits from English
78 Solution: Flip Binary Tree To Match Preorder Traversal
79 Solution: Russian Doll Envelopes
80 Solution: Stamping The Sequence
81 Solution: Palindrome Linked List
82 Solution: Ones and Zeroes
83 Solution: Longest Valid Parentheses
84 Solution: Design Circular Queue
85 Solution: Global and Local Inversions
86 Solution: Minimum Operations to Make Array Equal
87 Solution: Determine if String Halves Are Alike
88 Solution: Letter Combinations of a Phone Number
89 Solution: Verifying an Alien Dictionary
90 Solution: Longest Increasing Path in a Matrix
91 Solution: Deepest Leaves Sum
92 Solution: Beautiful Arrangement II
93 Solution: Flatten Nested List Iterator
94 Solution: Partition List
95 Solution: Fibonacci Number
96 Solution: Remove All Adjacent Duplicates in String II
97 Solution: Number of Submatrices That Sum to Target
98 Solution: Remove Nth Node From End of List
99 Solution: Combination Sum IV
100 Solution: N-ary Tree Preorder Traversal
101 Solution: Triangle
102 Solution: Brick Wall
103 Solution: Count Binary Substrings
104 Solution: Critical Connections in a Network
105 Solution: Rotate Image
106 Solution: Furthest Building You Can Reach
107 Solution: Power of Three
108 Solution: Unique Paths II
109 Solution: Find First and Last Position of Element in Sorted Array
110 Solution: Powerful Integers
111 Solution: Prefix and Suffix Search
112 Solution: Course Schedule III
113 Solution: Running Sum of 1d Array
114 Solution: Non-decreasing Array
115 Solution: Jump Game II
116 Solution: Convert Sorted List to Binary Search Tree
117 Solution: Delete Operation for Two Strings
118 Solution: Super Palindromes
119 Solution: Construct Target Array With Multiple Sums
120 Solution: Count Primes
121 Solution: Maximum Points You Can Obtain from Cards
122 Solution: Range Sum Query 2D – Immutable
123 Solution: Ambiguous Coordinates
124 Solution: Flatten Binary Tree to Linked List
125 Solution: Valid Number
126 Solution: Binary Tree Cameras
127 Solution: Longest String Chain
128 Solution: Find Duplicate File in System
129 Solution: Minimum Moves to Equal Array Elements II
130 Solution: Binary Tree Level Order Traversal
131 Solution: Find and Replace Pattern
132 Solution: N-Queens
133 Solution: To Lower Case
134 Solution: Evaluate Reverse Polish Notation
135 Solution: Partitioning Into Minimum Number Of Deci-Binary Numbers
136 Solution: Maximum Product of Word Lengths
137 Solution: Maximum Erasure Value
138 Solution: N-Queens II
139 Solution: Maximum Gap
140 Solution: Search Suggestions System
141 Solution: Max Area of Island
142 Solution: Interleaving String
143 Solution: Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts
144 Solution: Open the Lock
145 Solution: Maximum Performance of a Team
146 Solution: Longest Consecutive Sequence
147 Solution: Min Cost Climbing Stairs
148 Solution: Construct Binary Tree from Preorder and Inorder Traversal
149 Solution: Jump Game VI
150 Solution: My Calendar I
151 Solution: Stone Game VII
152 Solution: Minimum Number of Refueling Stops
153 Solution: Palindrome Pairs
154 Solution: Maximum Units on a Truck
155 Solution: Matchsticks to Square
156 Solution: Generate Parentheses
157 Solution: Number of Subarrays with Bounded Maximum
158 Solution: Swim in Rising Water
159 Solution: Pascal’s Triangle
160 Solution: Out of Boundary Paths
161 Solution: Redundant Connection
暂无评论内容