Construct a special tree from given preorder traversal
Given an array ‘pre[]’ that represents Preorder traversal of a spacial binary tree where every node has either 0 or 2 children. One more array ‘preLN[]’ is given which has only two possible values ‘L’ and ‘N’. The value ‘L’ in ‘preLN[]’ indicates that the corresponding node in Binary Tree is a leaf node and value ‘N’ indicates that the corresponding node is non-leaf node. Write a function to construct the tree from the given two arrays.
Example:
Input: pre[] = {10, 30, 20, 5, 15}, preLN[] = {'N', 'N', 'L', 'L', 'L'}
Output: Root of following tree
10
/ \
30 15
/ \
20 5
class Solution {
static int index;
private static Node helper(int[] preData, String[] lnData) {
if (index >= preData.length)
return null;
if (lnData[index].equals("L"))
return new Node(preData[index++], null, null);
Node root = new Node(preData[index++], null, null);
root.left = helper(preData, lnData);
root.right = helper(preData, lnData);
return root;
}
private static Node construct(int[] preData, String[] lnData) {
index = 0;
return helper(preData, lnData);
}
}
Last updated