[LeetCode] Construct Binary Tree from Preorder and Inorder Traversal 순서와 순서에 따라 두 갈래 트리를 복원합니다.

제목: Construct Binary Tree from Preorder and Inorder Traversal
<span style="font-size:18px;">/**LeetCode 
 *  : , 
 *  : , , 
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
package javaTrain;

public class Train20 {
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		int n = preorder.length;
		if(n == 0) return null;
		int m = 0;
		int num = preorder[0];
		boolean tag = true;
		for(int i = 0;i < n;i++){ 
			if(inorder[i] == num)
				break;
			m++;
		}
		int[] leftPre = new int[m];
		int[] leftIn = new int[m];
		int[] rightPre = new int[m-n-1];
		int[] rightIn = new int[m-n-1];
		for(int j = 0;j < n;j++){
			if(j == num-1) tag = false;
			if(tag){
				leftIn[j] = inorder[j];
				leftPre[j] = preorder[j+1];
			}
			else{
				rightIn[j-num-1] = inorder[j];
				rightPre[j] = preorder[j+1];
			}
		}
		TreeNode root = new TreeNode(num);
		root.left = buildTree(leftPre,leftIn);
		root.right = buildTree(rightPre,rightIn);
		return root;
    }
}
</span>

좋은 웹페이지 즐겨찾기