【一刷《剑指Offer》】面试题 6:重建二叉树

简介: 【一刷《剑指Offer》】面试题 6:重建二叉树

力扣对应链接:105. 从前序与中序遍历序列构造二叉树 - 力扣(LeetCode)

牛客对应链接:重建二叉树_牛客题霸_牛客网 (nowcoder.com)

核心考点:二叉树重建,遍历理解,递归。  


一、《剑指Offer》内容


二、分析问题

【经典二叉树问题】

根据 root 节点,将中序 vector 根据根节点划分为:左中序、右中序。

根据中序子序列长度,将前序 vector 划分为:根节点、左子树前序、右子树前序。

root->left 递归生成。

root->right 递归生成。


三、代码

//力扣AC的代码
/**
 * 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* traversal(vector<int>& preorder, int pre_st, int pre_ed, vector<int>& inorder, int in_st, int in_ed)
    {
        if(pre_st>pre_ed || in_st>in_ed) return nullptr;
        TreeNode* root=new TreeNode(preorder[pre_st]);
        for(int i=0; i<inorder.size(); i++)
        {
            if(inorder[i]==preorder[pre_st])
            {
                root->left=traversal(preorder, pre_st+1, (pre_st+1)+(i-in_st)-1, inorder, in_st, i-1);
                root->right=traversal(preorder, (pre_st+1)+(i-in_st-1)+1, pre_ed, inorder, i+1, in_ed);
                break;
            }
        }
        return root; 
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n=preorder.size(), m=inorder.size();
        return traversal(preorder, 0, n-1, inorder, 0, m-1);
    }
};
 
//力扣AC的代码(化简)
/**
 * 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* traversal(vector<int>& preorder, int pre_st, int pre_ed, vector<int>& inorder, int in_st, int in_ed)
    {
        if(pre_st>pre_ed || in_st>in_ed) return nullptr;
        TreeNode* root=new TreeNode(preorder[pre_st]);
        for(int i=0; i<inorder.size(); i++)
        {
            if(inorder[i]==preorder[pre_st])
            {
                root->left=traversal(preorder, pre_st+1, pre_st+i-in_st, inorder, in_st, i-1);
                root->right=traversal(preorder, pre_st+i-in_st+1, pre_ed, inorder, i+1, in_ed);
                break;
            }
        }
        return root; 
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n=preorder.size(), m=inorder.size();
        return traversal(preorder, 0, n-1, inorder, 0, m-1);
    }
};
 
//牛客AC的代码
/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param preOrder int整型vector 
     * @param vinOrder int整型vector 
     * @return TreeNode类
     */
    TreeNode* traversal(vector<int>& preOrder, int pre_st, int pre_ed, vector<int>& vinOrder, int in_st, int in_ed)
    {
        if(pre_st>pre_ed || in_st>in_ed) return nullptr;
        TreeNode* root=new TreeNode(preOrder[pre_st]);
        for(int i=0; i<vinOrder.size(); i++)
        {
            if(vinOrder[i]==preOrder[pre_st])
            {
                root->left=traversal(preOrder, pre_st+1, pre_st+i-in_st, vinOrder, in_st, i-1);
                root->right=traversal(preOrder, pre_st+i-in_st+1, pre_ed, vinOrder, i+1, in_ed);
                break;
            }
        }
        return root; 
    }
    TreeNode* reConstructBinaryTree(vector<int>& preOrder, vector<int>& vinOrder) {
        int n=preOrder.size(), m=vinOrder.size();
        return traversal(preOrder, 0, n-1, vinOrder, 0, m-1);
    }
};

四、细节处理

注意:这上面的代码采用的都是左闭右闭区间,所以在计算长度的时候要格外注意,建议通过画图来解决问题。

在递归左子树的参数中,前序遍历的终点值需要依靠中序遍历中根节点前面左中序的数量。而在递归右子树的参数中,前序遍历的起点值是左子树前序遍历终点值再 +1。


五、扩展

类似问题:106. 从中序与后序遍历序列构造二叉树 - 力扣(LeetCode)

/**
 * 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* traversal(vector<int>& inorder, int in_st, int in_ed, vector<int>& postorder, int post_st, int post_ed)
    {
        if(in_st>in_ed || post_st>post_ed) return nullptr;
        TreeNode* root=new TreeNode(postorder[post_ed]);
        for(int i=0; i<inorder.size(); i++)
        {
            if(inorder[i]==postorder[post_ed])
            {
                root->left=traversal(inorder, in_st, i-1, postorder, post_st, post_st+(i-in_st)-1);
                root->right=traversal(inorder, i+1, in_ed, postorder, post_st+(i-in_st), post_ed-1);
                break;
            }
        }
        return root; 
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n=inorder.size(), m=postorder.size();
        return traversal(inorder, 0, n-1, postorder, 0, m-1);
    }
};

通过先序与后序遍历可以构造二叉树吗?

不一定可以。

为什么先序 + 后序不一定能推出二叉树?可参考以下例子:

在上图(1)(2)中,先序遍历的结果都是 AB,后序遍历的结果都是 BA,然而对应了两种结构,故无法判定;

但当先序序列是 ABC,后序序列是 BAC 时,唯一确定了图(3)。


相关文章
|
2月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
2月前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
2月前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
2月前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
2月前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
2月前
【一刷《剑指Offer》】面试题 18:树的子结构
【一刷《剑指Offer》】面试题 18:树的子结构
|
2月前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
|
2月前
【一刷《剑指Offer》】面试题 16:反转链表
【一刷《剑指Offer》】面试题 16:反转链表
|
2月前
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15:链表中倒数第 k 个结点
|
2月前
|
C++
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面
【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面