• 关键字:二叉树
  • 难度:中等
  • 前置知识:二叉树、分治
  • 题目大意:对于给出的一棵二叉树的前序遍历和中序遍历,还原这棵二叉树

题目描述

Given preorder and inorder traversal of a tree, construct the binary tree.

解法

相信学过数据结构的同学应该都对这道题目有深刻的印象,虽然它是二叉树的题目,但是其更多使用到的还是分治的思想。

对于给定的前序遍历preorder和中序遍历inorder,首先我们不难发现,这棵树的根结点其实就是preorder[0]。由于preorderinorder是对同一棵树的遍历,我们可以知道preorder[0]inorder中一定也存在,不妨设preorder[0]==inorder[k]

由于inorder是中序遍历,所以k左边的就是根节点左子树的中序遍历、k右边的就是根节点右子树的中序遍历。

并且,由于我们已经知道了根节点左子树的节点数(与中序遍历长度相同),不妨设为l,我们可以知道preorder1l+1就是根节点左子树的前序遍历,剩下的最后一部分就是根节点右子树的前序遍历。

也就是说,我们可以计算出左子树、右子树的前序遍历和中序遍历,从而可以用分治的思想,将规模较大的问题分解成为两个较小的问题,然后递归的进行处理,还原左子树和右子树,最后连通根节点一起组成一棵完整的树。

因为过程实际上很简单~建议同代码一起参考~

参考代码

/**
 * 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) {
        return work(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
    }

    // 为了避免数组的复杂操作,这里直接用左右界和数组的引用来代表一段前序遍历和中序遍历
    // 即preorder[lp, rp]代表了当前子树的前序遍历,inorder[li, ri]代表了当前子树的中序遍历
    TreeNode* work(vector<int>& preorder, vector<int>& inorder, int lp, int rp, int li, int ri) {
        // 判断长度为0的情况
        if (lp > rp) return NULL;
        // 设置根节点
        TreeNode *root = new TreeNode(preorder[lp]);
        // 找到根节点在inorder中的位置
        for (int k = li; k <= ri; k++) {
            if (preorder[lp] == inorder[k]) {
                // 分治处理两棵子树
                root -> left = work(preorder, inorder, lp + 1, lp + (k - li), li, k - 1);
                root -> right = work(preorder, inorder, lp + (k - li) + 1, rp, k + 1, ri);
            }
        }
        // 返回这棵子树
        return root;
    }
};

登录发表评论 注册

反馈意见