Last active
April 16, 2020 11:15
-
-
Save tonymontaro/0a53e781cdb2b9a038ec679d2bc0762b to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Program { | |
| public static BinaryTree flattenBinaryTree(BinaryTree node) { | |
| // O(n) time | O(d) space d -> depth of tree | |
| flatten(node, null, null); | |
| while (node.left != null) node = node.left; | |
| return node; | |
| } | |
| static void flatten(BinaryTree node, BinaryTree left, BinaryTree right) { | |
| boolean isLeftMost = node.left == null && left != null; | |
| boolean isRightMost = node.right == null && right != null; | |
| boolean shouldExploreLeft = node.left != null; | |
| boolean shouldExploreRight = node.right != null; | |
| if (isLeftMost) { | |
| node.left = left; | |
| left.right = node; | |
| } else if (shouldExploreLeft) flatten(node.left, left, node); | |
| if (isRightMost) { | |
| node.right = right; | |
| right.left = node; | |
| } else if (shouldExploreRight) flatten(node.right, node, right); | |
| } | |
| // This is the class of the input root. Do not edit it. | |
| static class BinaryTree { | |
| int value; | |
| BinaryTree left = null; | |
| BinaryTree right = null; | |
| public BinaryTree(int value) { | |
| this.value = value; | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment