선순과 중순으로 두 갈래 나무를 세우다

1546 단어

Construct Binary Tree from Preorder and Inorder Traversal

 
Given preorder and inorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree. 
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
     static int getRootIndexInOrder(int inorder[], int root, int l, int r) {
        while (l <= r) {
            if (inorder[l] != root)
                l++;
            else break;
        }
        return l > r ? -1 : l;
    }

    static TreeNode create(int preorder[], int inorder[], int l1, int r1, int l2, int r2) {
        if (l1 > r1) return null;
        int root = preorder[l1];
        int index = getRootIndexInOrder(inorder, root, l2, r2);
        TreeNode rootNode = new TreeNode(root);

        TreeNode lchild = create(preorder, inorder, l1 + 1, l1 + index - l2, l2, index - 1);
        TreeNode rchild = create(preorder, inorder, l1 + index - l2 + 1, r1, index + 1, r2);

        rootNode.left = lchild;
        rootNode.right = rchild;
        return rootNode;
    }

     public TreeNode buildTree(int[] preorder, int[] inorder) {
        return create(preorder,inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }
}
leetCode 110. Balanced Binary Tree 밸런스 트리
606. Construct String from Binary Tree 두 갈래 트리의 문자열 설명

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage