In this Leetcode Flatten Binary Tree to Linked List problem solution we have 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.
Problem solution in Python.
def flatten(self, root): if not root: return left, right = root.left, root.right self.flatten(left) self.flatten(right) root.left = None if left: root.right = left while root.right: root = root.right root.right = right
Problem solution in Java.
public void flatten(TreeNode root) { if(root == null) return; flatten(root.left); flatten(root.right); TreeNode temp_right = root.right; root.right = root.left; root.left = null; while(root.right != null) root = root.right; root.right = temp_right; root.left = null; }
Problem solution in C++.
class Solution { private: TreeNode* flatTree(TreeNode *root) { if(!root->left && !root->right) return root; if(!root->right) { root->right = root->left; root->left = NULL; return flatTree(root->right); } if(!root->left) return flatTree(root->right); TreeNode* oldRight = root->right; root->right = root->left; (flatTree(root->right))->right = oldRight; root->left = NULL; return flatTree(root->right); } public: void flatten(TreeNode *root) { if(!root) return; flatTree(root); } };
Problem solution in C.
struct TreeNode* prev = NULL; void flatten(struct TreeNode* root){ if (root == NULL){ return; } flatten(root->right); flatten(root->left); root->right = prev; root->left = NULL; prev = root; }
0 Comments