32일 (106. Construct Binary Tree from Inorder and Postorder Traversal) 트리, 재귀, 순회

Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.


Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

 

Example 2:
Input: inorder = [-1], postorder = [-1]
Output: [-1]
 

Constraints:
1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder and postorder consist of unique values.
Each value of postorder also appears in inorder.
inorder is guaranteed to be the inorder traversal of the tree.
postorder is guaranteed to be the postorder traversal of the tree.

 

 

어떤 이진트리를 중위순회(inorder), 후위순회(postorder) 하였을때의 값을 입력받았을 때 해당 이진트리를 반환해야한다.

 

트리의 순회 방법으로 전위순회(preorder), 중위순회(inorder), 후위순회(postorder)  가 있다.

쉽게 외우는 방법은 중앙노드를 언제 방문하느냐를 기준으로 외우면 된다.

>> 전위순회는 중 왼 오, 중위순회는 왼 중 오, 후위순회는 왼 오 중 순서로 방문한다.

 

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
    class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {

            return buildTree(inorder,0, inorder.length-1, postorder, 0 , postorder.length-1);
        }

        private TreeNode buildTree(int[] inorder, int inStart, int inEnd, 
        int[] postorder, int postStart, int postEnd) {
            
            if (inStart > inEnd || postStart > postEnd) return null; // Base case

            int rootVal = postorder[postEnd]; // 1
            TreeNode rootNode = new TreeNode(rootVal);

            int rootIdxAtInorder = 0; // 2
            for(int i = 0 ; i <= inEnd; i++) {
                if(rootVal == inorder[i]) {
                    rootIdxAtInorder = i;
                    break;
                }
            }

            // 3
            int leftSize = rootIdxAtInorder - inStart;
            int rightSize = inEnd - rootIdxAtInorder;

            rootNode.left = buildTree(inorder, inStart, rootIdxAtInorder - 1,
                    postorder, postStart, postStart + leftSize -1); // 3-1

            rootNode.right = buildTree(inorder, rootIdxAtInorder + 1, inEnd,
                    postorder, postEnd - rightSize, postEnd - 1); // 3-2
            

            return rootNode;
        }

    }

 

0. 결론부터 이야기하자면 루트노드를 기준으로 양쪽으로 계속 나누어갈 것인데, 배열의 왼쪽인덱스가 오른쪽인덱스가 침범하기 전까지(0번의 기준에 도달할 때까지) 3번의 재귀함수를 호출 할 것이다.

 

1. postorder의 경우 순회방법은 왼 -> 오 -> 중 이다.

루트노드의 왼쪽리프노드들을 전부 순회하고, 오른쪽리프노드를 전부 순회 후 마지막으로 루트노드를 방문한다.

그렇기 때문에 postorder배열의 마지막 요소는 구하고자하는 트리의 루트노드의 값이 된다.

 

2. inorder의 경우 순회방법은 왼 -> 중 -> 오 이다.

그렇기 때문에 루트노드의 인덱스를 찾는다면, 루트노드 인덱스 - 1은 왼쪽리프노드들이 되고 루트노드 인덱스 + 1은 오른쪽리프노드들이 된다.

 

3. 이제 루트노드를 제외한 양쪽노드들의 크기를 상대적으로 구할 수 있다.

왼쪽 리프노드들(leftSize) 의 경우 rootIdxAtInorder의 왼쪽 인덱스가 될 테고,

오른쪽 리프노드들(rightSize)의 경우 인덱스의 끝에서 rootIdxAtInorder+1까지의 값이 될 것이다.

 

3-1. 3-2 루트노드의 위치와 값을 구했으며, 그 후 양쪽 노드들을

최대한 왼쪽 탐색 -> Base case에 걸린다면 그 후 오른쪽 탐색 후 병합

 

4. 모든 함수들이 종료되고 트리를 반환하면 끝.

 

 

 

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

Construct Binary Tree from Inorder and Postorder Traversal - LeetCode