전차와 중차 반복 구조 두 갈래 나무

1. 제목 설명

1. 문제 풀이

문제 풀이 사고방식

코드 구현

public class ConstructTreeFromPreAndIn {


    /** * 1.  inorder root ， 。 * 2.   */
    public TreeNode buildTree(int[] preorder, int[] inorder) {

        if(preorder == null || inorder == null || preorder.length != inorder.length || preorder.length == 0)
            return null;
        return buildTreeCore(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
    }

    public TreeNode buildTreeCore(int[] preorder, int s1, int e1, int[] inorder, int s2, int e2) {

        if(s1 > e1 || s2 > e2)
            return null;
        TreeNode root = new TreeNode(preorder[s1]);

        // root 
        int rootIndex = -1;
        for(int i = s2; i <= e2; i++) {
            if(inorder[i] == root.val) {
                rootIndex = i;
                break;
            }
        }
        if(rootIndex == -1)
            return null;

        int leftSize = rootIndex - s2;
        int rightSize = e2 - rootIndex;
        // 
        root.left = buildTreeCore(preorder, s1 + 1, s1 + leftSize, inorder, s2, rootIndex - 1);
        root.right = buildTreeCore(preorder, e1-rightSize+1, e1, inorder, rootIndex+1, e2);

        return root;
    }

    // 
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }
}