• LeetCode 105. 从前序与中序遍历序列构造二叉树(Construct Binary Tree from Preorder and Inorder Traversal)


    题目描述

    根据一棵树的前序遍历与中序遍历构造二叉树。

    注意:
    你可以假设树中没有重复的元素。

    例如,给出

    前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]

    返回如下的二叉树:

        3
       / 
      9  20
        /  
       15   7

    解题思路

    利用回溯的思想,分别记录生成树时前序遍历和中序遍历对应的段首、段尾,每次构造树时首先构造根节点为前序遍历的首节点,接着在中序遍历序列中找到根的位置,然后根左对应左子树,根右对应右子树,对应到前序遍历序列中分隔成两段,递归构造左子树和右子树。

    代码

     1 /**
     2  * Definition for a binary tree node.
     3  * struct TreeNode {
     4  *     int val;
     5  *     TreeNode *left;
     6  *     TreeNode *right;
     7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     8  * };
     9  */
    10 class Solution {
    11 public:
    12     TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    13         return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    14     }
    15     TreeNode* build(vector<int> preorder, vector<int> inorder, int pLeft, int pRight, int iLeft, int iRight){
    16         if(pLeft > pRight) return NULL;
    17         TreeNode* root = new TreeNode(preorder[pLeft]);
    18         int idx = iLeft;
    19         while(inorder[idx] != preorder[pLeft]) idx++;
    20         root->left = build(preorder, inorder, pLeft + 1, pLeft + idx - iLeft, iLeft, idx - 1);
    21         root->right = build(preorder, inorder, pLeft + idx - iLeft + 1, pRight, idx + 1, iRight);
    22         return root;
    23     }
    24 };
  • 相关阅读:
    【CSP-S膜你考】不怕噩梦 (模拟)
    【CSP-S膜你考】 A
    【CSP-S膜你考】即时战略(模拟)
    【CSP-S膜你考】最近公共祖先 (数学)
    【题解】洛谷 P1449 后缀表达式
    【题解】 洛谷 P2649 游戏预言
    【题解】洛谷 P1083 借教室
    【题解】洛谷 P1080 国王游戏
    【题解】洛谷 P1079 Vigenère 密码
    Bzoj4558 [JLoi2016]方
  • 原文地址:https://www.cnblogs.com/wmx24/p/9510314.html
一二三 - 开发者的网上家园