Java - Easy recursive solution


  • 0
    G
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
    		return buildTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    	}
    
    	private TreeNode buildTree(int[] preorder, int[] inorder, int iPre, int jPre, int iIor, int jIor) {
    		if (iPre > jPre || iIor > jIor) return null;
    		TreeNode root = new TreeNode(preorder[iPre]);
    		int indexOfRoot = -1;
    		for (int i = iIor; i <= jIor && i < inorder.length; i++) {
    			if (inorder[i] == root.val) {
    				indexOfRoot = i;
    				break;
    			}
    		}
    		root.left = buildTree(preorder, inorder, iPre + 1, iPre + (indexOfRoot - iIor), iIor, indexOfRoot - 1);
    		root.right = buildTree(preorder, inorder, iPre + (indexOfRoot - iIor) + 1, jPre, indexOfRoot + 1, jIor);
    		return root;
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.