leetcode 105.从前序与中序遍历序列构造二叉树

题目描述

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

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

例如，给出

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

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

解题思路

前序、中序、后序三种遍历的结构中，其中可以确定一个唯一的二叉树的组合包括 （前序、中序）、（中序、后序）。该题是前序、中序确定一个二叉树，其中前序提供一个根节点，可以在中序中找到对应的位置，该元素又会把中序分成两个子数组，每个子数组又可以找到对应的前序子数组，递归下去，就可以找到每一个节点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 数组是否为空
        if(preorder.size() == 0 || inorder.size() == 0){
            return NULL;
        }
		// 调用递归
        return build(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
    }
    
    /*
    *递归函数：
    *参数从左至右依次是：前序、中序、前序左起点、前序尾部、中序左起点、中序尾部
    */
    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int preLeft, int preRight, int inLeft, int inRight) {
        // 如果任何一个尾部的下标大于起点，直接返回
        if(preLeft > preRight || inLeft > inRight){
            return NULL;
        }

        // 建立一个新的树
        TreeNode* root = new TreeNode(preorder[preLeft]);

        // 定义一个变量，用于记录前序的元素在中序中的位置
        int index = inLeft;
        while(index <= inRight && preorder[preLeft] != inorder[index]){
            index++;
        }
        // 计算左子树的长度，通过尾部下标可以计算出来右子树的长度
        int len = index-inLeft;
        // 递归，查找左子树和右子树
        root->left = build(preorder, inorder, preLeft+1, preLeft+len, inLeft, inLeft+len-1);
        root->right = build(preorder, inorder, preLeft+len+1, preRight, inLeft+len+1, inRight);

        return root;
    }
};

欢迎大家关注我的个人公众号，同样的也是和该博客账号一样，专注分享技术问题，我们一起学习进步