Created
November 21, 2021 01:05
-
-
Save ssshukla26/8691e75b1fa5d529954c504513fb0683 to your computer and use it in GitHub Desktop.
Build Tree From Preorder and Postorder given Inorder [LeetCode 105/106]
This file contains 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
| # 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 buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]: | |
| root = None | |
| if inorder and postorder: | |
| # Get the current root we are looking for | |
| val = postorder[-1] | |
| # Find the index of the root in inorder list, this is the same index | |
| # in the postorder to divide the list | |
| idx = inorder.index(val) | |
| # Make root with the current value | |
| root = TreeNode(val) | |
| # Make left subtree, take inorder upto index and postorder upto index | |
| root.left = self.buildTree(inorder[:idx], postorder[:idx]) | |
| # Make right subtree, take inorder from the next index and postorder | |
| # from the current index to the second last index | |
| root.right = self.buildTree(inorder[idx+1:], postorder[idx:-1]) | |
| return root |
This file contains 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
| # 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: | |
| root = None | |
| if inorder and preorder: | |
| # Get the current root we are looking for | |
| val = preorder[0] | |
| # Find the index of the root in inorder list, this is the same index | |
| # in the preorder to divide the list | |
| idx = inorder.index(val) | |
| # Make root with the current value | |
| root = TreeNode(val) | |
| # Make left subtree, take inorder upto index and preorder from the first | |
| # upto the current index | |
| root.left = self.buildTree(preorder[1:idx+1], inorder[:idx]) | |
| # Make right subtree, take inorder from the next index and preorder | |
| # from the next index | |
| root.right = self.buildTree(preorder[idx+1:], inorder[idx+1:]) | |
| return root |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment