From INORDER and POSTORDER

Given two integer arrays `inorder` and `postorder` where `inorder` is the inorder traversal of a binary tree and `postorder` is the postorder traversal of the same tree, construct and return the binary tree.

Algorithm:

In Postorder, the rightmost element is the root. Search this root in inorder array .Let that index be i ,then left side of i is left subtree and right side of i is right subtree. We use postorder array to create nodes but to construct tree we use inorder array.

Code:

`class Solution {    int index;    public TreeNode buildTree(int[] inorder, int[] postorder) {        index= postorder.length-1;        return build(postorder,inorder,0,postorder.length-1);    }    public TreeNode build(int[] post, int[] in, int start, int end){        if(start>end){            return null;        }        TreeNode node = new TreeNode(post[index]);        index--;                int inIndex=search(in,start,end,node.val);                node.right=build(post,in,inIndex+1,end);        node.left=build(post,in,start,inIndex-1);        return node;            }    public int search(int arr[], int strt, int end, int value)    {        int i;        for (i = strt; i <= end; i++) {            if (arr[i] == value)                return i;        }        return i;    }}`

From INORDER and PREORDER

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.

Code:

`class Solution {    int index=0;    public TreeNode buildTree(int[] preorder, int[] inorder) {        return build(preorder,inorder,0,preorder.length-1);    }    public TreeNode build(int[] pre, int[] in, int start, int end){        if(start>end){            return null;        }        TreeNode node = new TreeNode(pre[index]);        index++;        if(start==end){            return node;        }        int inIndex=search(in,start,end,node.val);        node.left=build(pre,in,start,inIndex-1);        node.right=build(pre,in,inIndex+1,end);        return node;            }    public int search(int arr[], int strt, int end, int value)    {        int i;        for (i = strt; i <= end; i++) {            if (arr[i] == value)                return i;        }        return i;    }}`

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.