LeetCode簡易問題解−105,106

105. Construct Binary Tree from Preorder and Inorder Traversal

タイトル説明:二叉木の先序遍歴配列と中序遍歴配列を与え、元の二叉木を構築する.構造体:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

基本思想は分治法であり,先序遍歴と中序遍歴の特性を利用した.最初にアクセスしたノードはルートノードである必要があります.(すなわち、配列の最初の値がルートノードの値)におけるシーケンスループの特性は、配列の値(現ノード)であり、左側の値はすべて現ノードの左サブツリーの値であり、右側の値はすべて現ノードの右サブツリーの値である.
具体的な方法は次のとおりです.

は、二叉木を正しく構築し、二叉木のルートノードを返す役割を果たす関数driverを定義する.

は、インデックスがindexのすべての現結点にある左サブツリーよりも小さいシーケンス配列の最初の値が中シーケンス配列の位置(index)を見つけ、この部分の配列を完全数の配列としてdriver(すなわち再帰)呼び出し、中シーケンス配列インデックスがindexより大きいサブ配列も同様にdriver関数に再帰的に使用する.

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return driver(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }
    TreeNode* driver(vector<int>& preorder, vector<int>& inorder, int p_lo, int p_hi, int i_lo, int i_hi) {
        //  ， 
        if (p_lo > p_hi) return NULL;
        if (p_lo == p_hi) return new TreeNode(preorder[p_lo]);
        int node_val = preorder[p_lo];
        int index_in = this->find(inorder, i_lo, i_hi, node_val);
        int pre_left_len = index_in - i_lo;
        TreeNode* node = new TreeNode(node_val);
        // preorder[p_lo+1 ... p_lo+pre_left_len] 。
        // inorder[i_lo ... index_in-1] 。
        node->left = driver(preorder, inorder, p_lo + 1, p_lo + pre_left_len, i_lo, index_in - 1);
        node->right = driver(preorder, inorder, p_lo + pre_left_len + 1, p_hi, index_in + 1, i_hi);
        return node;
    }
    int find(vector<int>& vec, int low, int high, int val) {
        for (int i = low; i <= high; ++i) {
            if (vec[i] == val) return i;
        }
        return -1;
    }
};

106. Construct Binary Tree from Inorder and Postorder Traversal

タイトル説明:中序配列と後序配列を与え、元の二叉木を構築する.
やり方は105題に似ていて、余計なことは言わない.
コードは次のとおりです.

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return driver(postorder, inorder, 0, postorder.size() - 1, 0, inorder.size() - 1);
    }
    TreeNode* driver(vector<int>& postorder, vector<int>& inorder, int p_lo, int p_hi, int i_lo, int i_hi) {
        if (p_lo > p_hi) return NULL;
        if (p_lo == p_hi) return new TreeNode(postorder[p_hi]);
        int node_val = postorder[p_hi];
        int index_in = this->find(inorder, i_lo, i_hi, node_val);
        int pre_left_len = index_in - i_lo;
        TreeNode* node = new TreeNode(node_val);
        node->left = driver(postorder, inorder, p_lo, p_lo + pre_left_len - 1, i_lo, index_in - 1);
        node->right = driver(postorder, inorder, p_lo + pre_left_len, p_hi - 1, index_in + 1, i_hi);
        return node;
    }
    int find(vector<int>& vec, int low, int high, int val) {
        for (int i = low; i <= high; ++i) {
            if (vec[i] == val) return i;
        }
        return -1;
    }
};