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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def buildTree(self, preorder, inorder):
9 def helper(preorder_start, preorder_end, inorder_start, inorder_end):
10 if preorder_start > preorder_end:
11 return None
12
13 root_val = preorder[preorder_start]
14 root = TreeNode(root_val)
15 inorder_root_index = inorder_index_map[root_val]
16 left_tree_size = inorder_root_index - inorder_start
17
18 root.left = helper(preorder_start + 1, preorder_start + left_tree_size, inorder_start, inorder_root_index - 1)
19 root.right = helper(preorder_start + left_tree_size + 1, preorder_end, inorder_root_index + 1, inorder_end)
20
21 return root
22
23 inorder_index_map = {value: idx for idx, value in enumerate(inorder)}
24 n = len(preorder)
25 return helper(0, n - 1, 0, n - 1)This Python solution defines a TreeNode class and constructs the tree using a helper function. The helper function takes indices to track the ranges in the preorder and inorder lists, creating new TreeNode objects as necessary and using an index map for efficient lookups. This approach recursively builds the tree, taking care of each node's 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.