Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree,
construct and return the binary tree.
Test Cases
Example 1:
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]
Example 2:
Input: preorder = [-1], inorder = [-1]
Output: [-1]
Solution
/**
* 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:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
return buildTree(preorder, inorder, 0, 0, inorder.size() - 1);
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, int prestart, int instart, int inend) {
if (prestart > preorder.size() || instart > inend) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[prestart]);
int index = instart;
while(index <= inend) {
if (inorder[index] == preorder[prestart]) {
break;
}
index++;
}
root->left = buildTree(preorder, inorder, prestart+1, instart, index-1);
root->right = buildTree(preorder, inorder, prestart+index-instart+1, index+1, inend);
return root;
}
};/**
* 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 TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder, inorder, 0, 0, inorder.length-1);
}
private TreeNode buildTree(int[] preorder, int[] inorder, int prestart, int instart, int inend) {
if (prestart > preorder.length || instart > inend) {
return null;
}
TreeNode root = new TreeNode(preorder[prestart]);
int inroot = instart;
while(inroot <= inend) {
if (inorder[inroot] == preorder[prestart]) {
break;
}
inroot++;
}
int count = inroot - instart;
root.left = buildTree(preorder, inorder, prestart+1, instart, inroot-1);
root.right = buildTree(preorder, inorder, prestart+inroot-instart+1, inroot+1, inend);
return root;
}
}from typing import List, 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
return self.helper(preorder, inorder, 0, 0, len(inorder) - 1)
def helper(self, preorder, inorder, prestart, instart, inend):
if prestart > len(preorder) or instart > inend:
return None
root = TreeNode(preorder[prestart])
index = instart
while index <= inend:
if inorder[index] == preorder[prestart]:
break
index += 1
root.left = self.helper(preorder, inorder, prestart+1, instart, index-1);
root.right = self.helper(preorder, inorder, prestart+index-instart+1, index+1, inend);
return root