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 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]
Explanation:
1
/ \
2 5
/ \ \
3 4 6
changes to
1
\
2
\
3
\
4
\
5
\
6
Example 2:
Input: root = []
Output: []
Solution
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
void flatten(struct TreeNode* root){
if (!root) return;
flatten(root->left);
flatten(root->right);
if (!root->left) return;
struct TreeNode* right = root->right;
struct TreeNode* left = root->left;
root->left = NULL;
root->right = left;
while(left->right != NULL) {
left = left->right;
}
left->right = right;
}/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void flatten(TreeNode* root) {
if (root == nullptr) return;
flatten(root->left);
flatten(root->right);
if (root->left == nullptr) return;
TreeNode* right = root->right;
TreeNode* left = root->left;
root->left = nullptr;
root->right = left;
while(left->right != nullptr) {
left = left->right;
}
left->right = right;
}
};/**
* 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;
flatten(root.left);
flatten(root.right);
if (root.left != null) {
TreeNode right = root.right;
TreeNode left = root.left;
root.left = null;
root.right = left;
while(left.right != null) {
left = left.right;
}
left.right = right;
}
}
}from typing import Optional
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if root is None:
return
self.flatten(root.left)
self.flatten(root.right)
if root.left is None:
return
right = root.right
left = root.left
root.left = None
root.right = left
while left.right is not None:
left = left.right
left.right = right