Sponsored
Sponsored
This approach uses recursion to build the tree. We know that the first element of the preorder traversal is the root of the tree. We find that element in the inorder traversal to determine the elements of the left and right subtrees. We then recursively build the left and right subtrees.
Steps:
Time Complexity: O(n), where n is the number of nodes in the tree, because each node is processed once.
Space Complexity: O(n) for the recursion call stack and additional structures.
1import java.util.HashMap;
2import java.util.Map;
3
4public class Solution {
5 public static class TreeNode {
6 int val;
7 TreeNode left;
8 TreeNode right;
9 TreeNode(int x) { val = x; }
10 }
11
12 private Map<Integer, Integer> inorderIndexMap;
13 private int preorderIndex;
14
15 public TreeNode buildTree(int[] preorder, int[] inorder) {
16 inorderIndexMap = new HashMap<>();
17 for (int i = 0; i < inorder.length; i++) {
18 inorderIndexMap.put(inorder[i], i);
19 }
20 preorderIndex = 0;
21 return buildTree(preorder, 0, inorder.length - 1);
22 }
23
24 private TreeNode buildTree(int[] preorder, int inorderStart, int inorderEnd) {
25 if (inorderStart > inorderEnd) {
26 return null;
27 }
28
29 int rootVal = preorder[preorderIndex++];
30 TreeNode root = new TreeNode(rootVal);
31 int inorderRootIndex = inorderIndexMap.get(rootVal);
32
33 root.left = buildTree(preorder, inorderStart, inorderRootIndex - 1);
34 root.right = buildTree(preorder, inorderRootIndex + 1, inorderEnd);
35
36 return root;
37 }
38}In this Java implementation, a TreeNode class is defined. The buildTree method initializes the preorderIndex and the index map for inorder elements. The recursive helper method constructs the tree by selecting the current root from the preorder array and dividing the inorder array elements around it to build left and right subtrees.
This approach uses an iterative method to build the binary tree using stacks. By leveraging the properties of the preorder and inorder sequences, we can keep track of the tree nodes that are yet to be processed. We utilize a stack data structure to maintain the hierarchy of nodes as they are constructed.
Steps:
Time Complexity: O(n), where n is the number of nodes, as each node is visited once.
Space Complexity: O(n) for the stack and additional data structures like the map for indices.
1#include <unordered_map>
2#include <vector>
3#include <stack>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty() || inorder.empty()) return nullptr;
unordered_map<int, int> inorderIndexMap;
for (int i = 0; i < inorder.size(); ++i) {
inorderIndexMap[inorder[i]] = i;
}
stack<TreeNode*> st;
TreeNode* root = new TreeNode(preorder[0]);
st.push(root);
int inorderIndex = 0;
for (int i = 1; i < preorder.size(); ++i) {
TreeNode* node = st.top();
if (inorderIndexMap[node->val] != inorderIndex) {
node->left = new TreeNode(preorder[i]);
st.push(node->left);
} else {
while (!st.empty() && inorderIndexMap[st.top()->val] == inorderIndex) {
node = st.top();
st.pop();
++inorderIndex;
}
node->right = new TreeNode(preorder[i]);
st.push(node->right);
}
}
return root;
}
};This C++ solution employs an iterative approach using a stack. By iterating through the preorder list, it constructs the tree and manages left and right children using the stack. This method avoids recursion and utilizes an index map for inorder positions.