[Binary Tree General][Medium] 106. Construct Binary Tree from Inorder and Postorder Traversal.

 

 

Q. inorder 와 postorder 순회 정보가 주어질 때 tree를 구성하라. 

 

 

Solution. 

 105번(https://artofcom77.tistory.com/258) 의 응용판 문제.

 

 여기서는 post order 정보를 사용하였으므로, 값을 뒤에서 부터 취하는 것이 중요. 

 또한 뒤에서 부터 취하므로, tree를 left -> right 가 아닌 그 역순(Right->Left)으로 더해 나가기 시작하는 것에 유의 한다. 

 

 코드 

 

 TreeNode BT(Dictionary<int, int> dictBuffer, int[] postorder, ref int idx, int left, int right)
{
    if(left > right)    return null;
    if(idx<0 || idx>=dictBuffer.Count)   return null;

    int val = postorder[postorder.Length-idx-1];
    int mid = dictBuffer[val];
    ++idx;

    TreeNode node = new TreeNode(val);
    // Right First !!!
    node.right = BT(dictBuffer, postorder, ref idx, mid+1, right);
    node.left  = BT(dictBuffer, postorder, ref idx, left, mid-1);
    return node;
}

public TreeNode BuildTree(int[] inorder, int[] postorder) 
{
    Dictionary<int, int> dictBuff = new Dictionary<int, int>();
    for(int q = 0; q < inorder.Length; ++q)
        dictBuff.Add( inorder[q], q );

    int idx = 0;
    return BT(dictBuff, postorder, ref idx, 0, dictBuff.Count-1);
}

 

 

 결과