題目

給定兩個整數(shù)數(shù)組 $preorder$ 和 $inorder$ ，其中 $preorder$ 是二叉樹的先序遍歷， $inorder$ 是同一棵樹的中序遍歷，請構造二叉樹并返回其根節(jié)點。文章來源地址http://www.zghlxwxcb.cn/news/detail-813712.html

復習

• 前序遍歷（先根遍歷）：遍歷順序為，根節(jié)點—左節(jié)點（左子樹）—右節(jié)點（右子樹）
• 中序遍歷（中根遍歷）：遍歷順序為，左節(jié)點（左子樹）—根節(jié)點—右節(jié)點（右子樹）
• 后序遍歷（后根遍歷）：遍歷順序為，左節(jié)點（左子樹）—右節(jié)點（右子樹）—根節(jié)點

思路—遞歸

• 對于任意一顆樹而言，前序遍歷的形式總是
  [ 根節(jié)點, [左子樹的前序遍歷結果], [右子樹的前序遍歷結果] ]
  • 也就是說對于前序遍歷序列，第一個必是根節(jié)點；第二個區(qū)間必是左子樹的前序遍歷序列；第三個區(qū)間必是右子樹的前序遍歷序列；
  • 問題是如何確定兩個區(qū)間的起止點（靠中序遍歷序列）
• 即根節(jié)點總是前序遍歷中的第一個節(jié)點。而中序遍歷的形式總是
  [ [左子樹的中序遍歷結果], 根節(jié)點, [右子樹的中序遍歷結果] ]
  • 根據(jù)前序遍歷序列找到根節(jié)點的位置，根節(jié)點前面的部分為左子樹的中序遍歷序列；后面的部分為右子樹的中序遍歷序列
  • 根據(jù)兩個中序遍歷序列的長度確定前序遍歷序列中兩個區(qū)間的起始點
• 對于每個子樹的前序遍歷與中序遍歷序列進行同樣的操作

代碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* subTree(vector<int>& preorder, vector<int>& inorder, int pre_l, int pre_r, int in_l, int in_r){
        if(pre_l == pre_r){
            return  new TreeNode(preorder[pre_l]);
        }
        int root_val = preorder[pre_l];
        TreeNode* root = new TreeNode(root_val);
        int tree_l_len = 0;
        for(int i = in_l; i <= in_r; i++){
            if(inorder[i] != root_val){
                tree_l_len++;
            }
            else{
                break;
            }
        }
        int tree_r_len = pre_r-pre_l-tree_l_len;
        if(tree_l_len>0){
            root->left = subTree(preorder, inorder, pre_l+1, pre_l+tree_l_len, in_l, in_l+tree_l_len-1);
        }
        if(tree_r_len>0){
            root->right = subTree(preorder, inorder, pre_l+tree_l_len+1, pre_r, in_r-tree_r_len+1, in_r);
        }
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        TreeNode* ret = subTree(preorder, inorder, 0, preorder.size()-1, 0, preorder.size()-1);
        return ret;
    }

};

到了這里，關于力扣_數(shù)組29—根據(jù)前序與中序遍歷序列構建二叉樹、根據(jù)中序與后序遍歷序列構建二叉樹的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！