算法4.前序中序重建二叉树 |

二叉树递归堆栈

算法

发布日期: 2020-09-20

更新日期: 2020-09-20

文章字数: 1.1k

阅读次数:

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1：

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

返回如下的二叉树：
    3
   / \
  9  20
    /  \
   15   7

解题思路

方法一：使用栈解决

时间复杂度：$O(N)$ 前序遍历和后序遍历都被遍历。

空间复杂度：$O(N)$ 额外使用栈存储已经遍历过的节点。

代码如下

class Solution {
public:
    map<int,int> map_inorder;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 前序：[3,9,20,15,7]
        // 中序：[9,3,15,20,7]
        if(inorder.size() == 0)
            return 0;

        for(int i=0; i<inorder.size(); i++){
            map_inorder[inorder[i]] = i;
        }

        TreeNode* root = new TreeNode();
        int left = 0;
        int part_root = 0;
        int right = inorder.size()-1;
        root = recure(part_root,left,right,preorder,inorder);
        // cout<<root->val<<endl;
        return root;
    }
    TreeNode* recure(int part_root,int left,int right,vector<int>& preorder,vector<int>& inorder){
        if(left>right) return 0;
        int mid = map_inorder[preorder[part_root]];
        // cout<<mid<<endl;
        TreeNode* root = new TreeNode();
        root->val = preorder[part_root];
        root->left = recure(part_root+1,left,mid-1,preorder,inorder);
        root->right = recure(part_root+1+mid-left,mid+1,right,preorder,inorder);
        return root;

    }
};

解法分析

如果使用栈来解决首先要搞懂一个知识点，就是前序遍历挨着的两个值比如m和n，他们会有下面两种情况之一的关系。

n是m左子树节点的值。
n是m右子树节点的值或者是m某个祖先节点的右节点的值。

解法注意点

根据中序队列首元素，遍历前序队列，不相等则入栈，并一直找到左子树。
若相等，则开始出栈，前进中序队列index，相等则不断出栈。
当有不相等，则说明该节点是父节点，将前序队列下一个节点放到这个节点的右子树上

方法二：递归

时间复杂度：$O(N)$

空间复杂度：$O(N)$

代码如下

class Solution {
public:
    map<int,int> map_inorder;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 前序：[3,9,20,15,7]
        // 中序：[9,3,15,20,7]
        if(inorder.size() == 0)
            return 0;

        for(int i=0; i<inorder.size(); i++){
            map_inorder[inorder[i]] = i;
        }

        TreeNode* root = new TreeNode();
        int left = 0;
        int part_root = 0;
        int right = inorder.size()-1;
        root = recure(part_root,left,right,preorder,inorder);
        // cout<<root->val<<endl;
        return root;
    }
    TreeNode* recure(int part_root,int left,int right,vector<int>& preorder,vector<int>& inorder){
        if(left>right) return 0;
        int mid = map_inorder[preorder[part_root]];
        // cout<<mid<<endl;
        TreeNode* root = new TreeNode();
        root->val = preorder[part_root];
        root->left = recure(part_root+1,left,mid-1,preorder,inorder);
        root->right = recure(part_root+1+mid-left,mid+1,right,preorder,inorder);
        return root;

    }
};

解法分析

递推参数：前序遍历中根节点的索引pre_root、中序遍历左边界in_left、中序遍历右边界in_right。
终止条件：当 in_left > in_right ，子树中序遍历为空，说明已经越过叶子节点，此时返回 $null$。
递推工作：
- 建立根节点root：值为前序遍历中索引为pre_root的节点值。
- 搜索根节点root在中序遍历的索引i：为了提升搜索效率，本题解使用哈希表 dic 预存储中序遍历的值与索引的映射关系，每次搜索的时间复杂度为 $O(1)$。
- 构建根节点root的左子树和右子树：通过调用 recur() 方法开启下一层递归。
  左子树：根节点索引为 pre_root + 1 ，中序遍历的左右边界分别为 in_left 和 i - 1。
  右子树：根节点索引为 i - in_left + pre_root + 1（即：根节点索引 + 左子树长度 + 1），中序遍历的左右边界分别为 i + 1 和 in_right。
返回值：返回 root，含义是当前递归层级建立的根节点 root 为上一递归层级的根节点的左或右子节点。