중차 범람과 후차 범람 트리 구조 두 갈래 나무

중차 역류와 후차 역류 트리에 따라 두 갈래 트리를 구성한다
예:
나무의 중서 역행을 제시한다:[1,2,3]과 후서 역행:[1,3,2]
다음 트리로 돌아갑니다.
 / \
1   3
전편의 를 참고하여 우리는 중서가 왼쪽->중->우이고, 후서가 왼쪽->우->중이라는 것을 안다.따라서 후차 역행의 마지막 값은 바로 뿌리 노드의 값이다. 이 값에 따라 우리는 중차 역행에서 뿌리 노드의 왼쪽 트리와 오른쪽 트리의 값을 찾아 왼쪽 트리와 오른쪽 트리를 구성하면 된다.

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
 

class Solution {
    /**
     *@param inorder : A list of integers that inorder traversal of a tree
     *@param postorder : A list of integers that postorder traversal of a tree
     *@return : Root of a tree
     */
public:

    TreeNode *construct(vector &inorder, vector &postorder, 
        int is, int ie, int ps, int pe) {
            TreeNode * root = new TreeNode(postorder[pe]);
            if (ps == pe) return root;
            int i;
            for (i = 0; i < ie; i++) {
                if (inorder[i] == root->val) break;
            }
            if (i-1 >= is) {
                root->left = construct(inorder, postorder, is, i-1, ps, ps+i-1-is);
            }
            if (i+1 <= ie) {
                root->right = construct(inorder, postorder, i+1, ie, ps+i-is, pe-1);
            }
            return root;            
        }


    TreeNode *buildTree(vector &inorder, vector &postorder) {
        if (inorder.empty() || postorder.empty() || 
            inorder.size() != postorder.size()) return NULL;
        return construct(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
    }
};