Thursday, August 18, 2016

Java Program: To Reconstruct A Binary Tree

This program is to reconstruct a binary tree according to its preorder and inorder traversals.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre==null)
             return null;
        TreeNode treeNode = new TreeNode(pre[0]);
        int i = 0;
        while (i<in.length&&in[i]!=pre[0])
            ++i;
        if (i>=in.length) {
        return null;
        }
        if (i>=1) {
        int[] preleft = new int[i];
        int[] inleft = new int[i];
        for(int j=0;j<i;++j) {
        preleft[j] = pre[j+1];
        inleft[j] = in[j];
        }
        treeNode.left = reConstructBinaryTree(preleft, inleft);
        } else {
        treeNode.left = null;
        }
        if (i<pre.length-1) {
       int[] preright = new int[pre.length-i-1];
       int[] inright = new int[pre.length-i-1];
       for(int j=0;j<pre.length-i-1;++j) {
           preright[j] = pre[i+j+1];
           inright[j] = in[i+j+1];
       }
       treeNode.right = reConstructBinaryTree(preright, inright);
        } else {
        treeNode.right = null;
        }
        return treeNode;
    }
}

No comments:

Post a Comment