Given the root of 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.
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
Follow up: Can you flatten the tree in-place (with O(1) extra space)?
Solution 1: Recursion
Time complexity: O(n)
Space complexity: O(|height|)
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# Author: Huahua class Solution: def flatten(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ def solve(root: Optional[TreeNode]): if not root: return None, None if not root.left and not root.right: return root, root l_head = l_tail = r_head = r_tail = None if root.left: l_head, l_tail = solve(root.left) if root.right: r_head, r_tail = solve(root.right) root.left = None root.right = l_head or r_head if l_tail: l_tail.right = r_head return root, r_tail or l_tail return solve(root)[0] |
Solution 2: Unfolding
Time complexity: O(n)
Space complexity: O(1)
Python3
|
1 2 3 4 5 6 7 8 9 10 11 |
# Author: Huahua class Solution: def flatten(self, root: Optional[TreeNode]) -> None: while root: if root.left: prev = root.left while prev.right: prev = prev.right prev.right = root.right root.right = root.left root.left = None root = root.right |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment