12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697
#include <bits/stdc++.h>
using namespace std;
// Definition for a binary tree node.
struct TreeNode {
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.empty() || postorder.empty() || inorder.size() != postorder.size()) {
return nullptr;
}
// Create a map to store the indices of elements in the inorder traversal
unordered_map<int, int> inorderMap;
for (int i = 0; i < inorder.size(); ++i) {
inorderMap[inorder[i]] = i;
}
// Call the recursive function to build the binary tree
return buildTreeHelper(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1, inorderMap);
}
private:
TreeNode* buildTreeHelper(vector<int>& inorder, int inStart, int inEnd,
vector<int>& postorder, int postStart, int postEnd,
unordered_map<int, int>& inorderMap) {
if (inStart > inEnd || postStart > postEnd) {
return nullptr;
}
// Create the root node from the last element in postorder
int rootValue = postorder[postEnd];
TreeNode* root = new TreeNode(rootValue);
// Find the index of rootValue in inorder to determine the left and right subtrees
int rootIndexInorder = inorderMap[rootValue];
int leftSubtreeSize = rootIndexInorder - inStart;
// Recursive calls to build left and right subtrees
root->left = buildTreeHelper(inorder, inStart, rootIndexInorder - 1,
postorder, postStart, postStart + leftSubtreeSize - 1, inorderMap);
root->right = buildTreeHelper(inorder, rootIndexInorder + 1, inEnd,
postorder, postStart + leftSubtreeSize, postEnd - 1, inorderMap);
return root;
}
};
// Function to print the inorder traversal of a tree
void printInorder(TreeNode* root) {
if (!root) {
return;
}
printInorder(root->left);
cout << root->data << " ";
printInorder(root->right);
}
// Function to print the given vector
void printVector(vector<int>& vec) {
for (int num : vec) {
cout << num << " ";
}
cout << endl;
}
int main() {
// Example input vectors
vector<int> inorder = {40, 20, 50, 10, 60, 30};
vector<int> postorder = {40, 50, 20, 60, 30, 10};
// Display the input vectors
cout << "Inorder Vector: ";
printVector(inorder);
cout << "Postorder Vector: ";
printVector(postorder);
Solution sol;
// Build the binary tree and print its inorder traversal
TreeNode* root = sol.buildTree(inorder, postorder);
cout << "Inorder of Unique Binary Tree Created: " << endl;
printInorder(root);
cout << endl;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112
import java.util.*;
class TreeNode {
int data;
TreeNode left;
TreeNode right;
TreeNode(int val) {
data = val;
left = null;
right = null;
}
}
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
if (inorder.length != postorder.length) {
return null;
}
// Create a map to store the indices
// of elements in the inorder traversal
Map<Integer, Integer> hm = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
hm.put(inorder[i], i);
}
// Call the recursive function
// to build the binary tree
return buildTreePostIn(inorder, 0, inorder.length - 1, postorder, 0,
postorder.length - 1, hm);
}
// Recursive function to build a binary
// tree from inorder and postorder traversals
public TreeNode buildTreePostIn(int[] inorder, int is, int ie,
int[] postorder, int ps, int pe, Map<Integer, Integer> hm) {
// Base case: If the subtree
// is empty, return null
if (ps > pe || is > ie) {
return null;
}
// Create a new TreeNode
// with the root value from postorder
TreeNode root = new TreeNode(postorder[pe]);
// Find the index of the root
// value in inorder traversal
int inRoot = hm.get(postorder[pe]);
// Number of nodes in the left subtree
int numsLeft = inRoot - is;
// Recursively build the
// left and right subtrees
root.left = buildTreePostIn(inorder, is, inRoot - 1, postorder,
ps, ps + numsLeft - 1, hm);
root.right = buildTreePostIn(inorder, inRoot + 1, ie, postorder,
ps + numsLeft, pe - 1, hm);
// Return the root of
// the constructed subtree
return root;
}
}
public class Main {
// Function to print the
// inorder traversal of a tree
public static void printInorder(TreeNode root) {
if (root == null) {
return;
}
printInorder(root.left);
System.out.print(root.data + " ");
printInorder(root.right);
}
// Function to print the given array
public static void printArray(int[] arr) {
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
public static void main(String[] args) {
// Example input arrays
int[] inorder = {40, 20, 50, 10, 60, 30};
int[] postorder = {40, 50, 20, 60, 30, 10};
// Display the input arrays
System.out.print("Inorder Array: ");
printArray(inorder);
System.out.print("Postorder Array: ");
printArray(postorder);
Solution sol = new Solution();
// Build the binary tree and
// print its inorder traversal
TreeNode root = sol.buildTree(inorder, postorder);
System.out.println("Inorder of Unique Binary Tree Created: ");
printInorder(root);
System.out.println();
}
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293
from typing import List
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.data = val
self.left = left
self.right = right
class Solution:
def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
if len(inorder) != len(postorder):
return None
# Create a map to store the indices
# of elements in the inorder traversal
hm = {}
for i, val in enumerate(inorder):
hm[val] = i
# Call the recursive function
# to build the binary tree
return self.buildTreePostIn(inorder, 0, len(inorder) - 1, postorder, 0,
len(postorder) - 1, hm)
# Recursive function to build a binary
# tree from inorder and postorder traversals
def buildTreePostIn(self, inorder: List[int], is_: int, ie: int,
postorder: List[int], ps: int, pe: int,
hm: dict) -> TreeNode:
# Base case: If the subtree
# is empty, return None
if ps > pe or is_ > ie:
return None
# Create a new TreeNode
# with the root value from postorder
root = TreeNode(postorder[pe])
# Find the index of the root
# value in inorder traversal
inRoot = hm[postorder[pe]]
# Number of nodes in the left subtree
numsLeft = inRoot - is_
# Recursively build the
# left and right subtrees
root.left = self.buildTreePostIn(inorder, is_, inRoot - 1, postorder,
ps, ps + numsLeft - 1, hm)
root.right = self.buildTreePostIn(inorder, inRoot + 1, ie, postorder,
ps + numsLeft, pe - 1, hm)
# Return the root of
# the constructed subtree
return root
def printInorder(root: TreeNode):
if not root:
return
printInorder(root.left)
print(root.data, end=" ")
printInorder(root.right)
def printList(lst: List[int]):
for num in lst:
print(num, end=" ")
print()
if __name__ == "__main__":
# Example input lists
inorder = [40, 20, 50, 10, 60, 30]
postorder = [40, 50, 20, 60, 30, 10]
# Display the input lists
print("Inorder List:", end=" ")
printList(inorder)
print("Postorder List:", end=" ")
printList(postorder)
sol = Solution()
# Build the binary tree and
# print its inorder traversal
root = sol.buildTree(inorder, postorder)
print("Inorder of Unique Binary Tree Created:")
printInorder(root)
print()
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104
/**
* Definition for a binary tree node.
*/
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.data = val;
this.left = left;
this.right = right;
}
}
class Solution {
buildTree(inorder, postorder) {
if (inorder.length !== postorder.length) {
return null;
}
// Create a map to store the indices
// of elements in the inorder traversal
let hm = new Map();
for (let i = 0; i < inorder.length; i++) {
hm.set(inorder[i], i);
}
// Call the recursive function
// to build the binary tree
return this.buildTreePostIn(inorder, 0, inorder.length - 1, postorder, 0,
postorder.length - 1, hm);
}
// Recursive function to build a binary
// tree from inorder and postorder traversals
buildTreePostIn(inorder, is, ie, postorder, ps, pe, hm) {
// Base case: If the subtree
// is empty, return null
if (ps > pe || is > ie) {
return null;
}
// Create a new TreeNode
// with the root value from postorder
let root = new TreeNode(postorder[pe]);
// Find the index of the root
// value in inorder traversal
let inRoot = hm.get(postorder[pe]);
// Number of nodes in the left subtree
let numsLeft = inRoot - is;
// Recursively build the
// left and right subtrees
root.left = this.buildTreePostIn(inorder, is, inRoot - 1, postorder,
ps, ps + numsLeft - 1, hm);
root.right = this.buildTreePostIn(inorder, inRoot + 1, ie, postorder,
ps + numsLeft, pe - 1, hm);
// Return the root of
// the constructed subtree
return root;
}
}
// Function to print the
// inorder traversal of a tree
function printInorder(root) {
if (!root) {
return;
}
printInorder(root.left);
process.stdout.write(root.data + " ");
printInorder(root.right);
}
// Function to print the given array
function printArray(arr) {
for (let num of arr) {
process.stdout.write(num + " ");
}
console.log();
}
// Example input arrays
let inorder = [40, 20, 50, 10, 60, 30];
let postorder = [40, 50, 20, 60, 30, 10];
// Display the input arrays
console.log("Inorder Array:", end=" ");
printArray(inorder);
console.log("Postorder Array:", end=" ");
printArray(postorder);
let sol = new Solution();
// Build the binary tree and
// print its inorder traversal
let root = sol.buildTree(inorder, postorder);
console.log("Inorder of Unique Binary Tree Created:");
printInorder(root);
console.log();
