LeetCode 105/106 Construct Binary Tree from Preorder/Postorder and Inorder Traversal

1: LeetCode 105 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.
링크:https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
분석: 이 문제는 두 갈래 나무의 전차와 중차가 두루 흐르는 결과로 이 두 갈래 나무를 구축하는 것이다

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void createTree(TreeNode *p, vector<int> &preorder, int pstart, int pend, vector<int> &inorder, int istart, int iend, int flag){
        if(pstart > pend) return;
        p = new TreeNode(preorder[pstart]);
        if(root == NULL) root = pNode = p;
        else{
            if(flag) pNode->right = p;     //   
            else pNode->left = p;
            pNode = p;
        }
        if(pstart == pend) return;
        int i = istart;
        for(; i <= iend; i++){
            if(inorder[i] == preorder[pstart])break;
        }
        int k = i - istart;    //  
        createTree(p->left, preorder, pstart+1, pstart+k, inorder, istart, i-1, 0);   //   flag=0 
        pNode = p;                    
        createTree(p->right, preorder, pstart+k+1, pend, inorder, i+1, iend, 1);     //   flag=1 
    }
    
    TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
        root = NULL;
        pNode = NULL;
        int n = preorder.size();
        if(n == 0) return root;
        createTree(root, preorder, 0, n-1, inorder, 0, n-1, 0);
        return root;
        
    }
private:
    TreeNode *root, *pNode;
};

2: Inorder and Postorder Traversal 의 LeetCode106 Construct Binary Tree
제목:
Given inorder and postorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
링크:https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/
분석: 이 문제는 중순과 후순이 두루 흐르는 결과로 두 갈래 트리를 구축한 것이다

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void createTree(TreeNode *p, vector<int> &inorder, int istart, int iend, vector<int> &postorder, int pstart, int pend, int flag){
        if(pstart > pend) return;
        p = new TreeNode(postorder[pend]);
        if(root == NULL) root = pNode = p;
        else{
            if(flag) pNode->right = p;    //   
            else pNode->left = p;
            pNode = p;
        }
        if(pstart == pend) return;
        int i = istart;
        for(; i<= iend; i++){
            if(inorder[i] == postorder[pend]) break;
        }
        int k = i - istart;
        createTree(p->left, inorder, istart, i-1, postorder, pstart, pstart+k-1, 0);   //  
        pNode = p;
        createTree(p->right, inorder, i+1, iend, postorder, pstart+k, pend-1, 1);   //  
        
    }
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
        root = pNode = NULL;
        int n = inorder.size();
        if(n == 0) return root;
        createTree(root, inorder, 0, n-1, postorder, 0, n-1, 0);
        return root;
        
        
    }
private:
    TreeNode *root, *pNode;

};