Leetcode[105, 106] Construct Binary Tree from Preorder and Inorder Traversal
07 Nov 2015###Task1 Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
###Python ####My solution: memory limit exceed!
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if not preorder or not inorder:
return None
if len(preorder) == 0 or len(inorder) == 0:
return None
root = TreeNode(preorder[0])
ind1 = inorder.index(preorder[0])
l = self.buildTree(preorder[1:ind1 + 1], inorder[:ind1])
r = self.buildTree(preorder[ind1 + 1:], inorder[ind1 + 1:])
root.left = l
root.right = r
return root
####another one
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def buildTree(self, preorder, inorder):
"""
:type preorder: List[int]
:type inorder: List[int]
:rtype: TreeNode
"""
if not preorder or not inorder:
return None
if len(preorder) == 0 or len(inorder) == 0:
return None
root = TreeNode(preorder.pop(0))
ind1 = inorder.index(root.val)
l = self.buildTree(preorder, inorder[:ind1])
r = self.buildTree(preorder, inorder[ind1 + 1:])
root.left = l
root.right = r
return root
###Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildHelper(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
if (inEnd < inStart || preEnd < preStart) {
return null;
}
TreeNode root = new TreeNode(preorder[preStart]);
int pos = 0;
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == preorder[preStart]) {
pos = i;
break;
}
}
//left
TreeNode left = buildHelper(preorder, preStart + 1, preStart + (pos - inStart), inorder, inStart, pos - 1);
root.left = left;
//right
TreeNode right = buildHelper(preorder, preStart + (pos - inStart) + 1, preEnd, inorder, pos + 1, inEnd);
root.right = right;
return root;
}
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) {
return null;
}
return buildHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
}
###Points
- O(n)
- Divide and conquer
- Python mem: pre list is not necessary sliced, cause it will be pop() every recursion; when the recursion reaches the end, pre list is empty.
- Python handy: list.index(num)
###Task2 Given inorder and postorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree. ###Python
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
if not inorder or not postorder:
return None
if len(inorder) == 0 or len(postorder) == 0:
return None
root = TreeNode(postorder.pop())
ind = inorder.index(root.val)
root.right = self.buildTree(inorder[ind + 1:], postorder)
root.left = self.buildTree(inorder[:ind], postorder)
return root
###Java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode buildHelper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {
if (inStart > inEnd || postStart > postEnd) {
return null;
}
TreeNode root = new TreeNode(postorder[postEnd]);
int pos = 0;
for (int i = 0; i < inorder.length; i++) {
if (inorder[i] == postorder[postEnd]) {
pos = i;
break;
}
}
TreeNode left = buildHelper(inorder, inStart, pos - 1, postorder, postStart, postStart + pos - inStart - 1);
TreeNode right = buildHelper(inorder, pos + 1, inEnd, postorder, postStart + pos - inStart, postEnd - 1);
root.left = left;
root.right = right;
return root;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder == null || postorder == null || inorder.length == 0 || postorder.length == 0) {
return null;
}
return buildHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
}
}
###Points
- O(n)
- In this case, since we need to pop() from the tail of postorder, the recursion should start from root.right and then root.left.