题目的主要信息:
  • 根据二叉树的前序遍历序列和中序遍历序列,重建该二叉树,并返回根节点
  • 两个遍历都没有重复的元素
举一反三:

学习完本题的思路你可以解决如下题目:

BM41. 输出二叉树的右视图

方法一:递归(推荐使用)

知识点:二叉树递归

递归是一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。因此递归过程,最重要的就是查看能不能讲原本的问题分解为更小的子问题,这是使用递归的关键。

而二叉树的递归,则是将某个节点的左子树、右子树看成一颗完整的树,那么对于子树的访问或者操作就是对于原树的访问或者操作的子问题,因此可以自我调用函数不断进入子树。

思路:

对于二叉树的前序遍历,我们知道序列的第一个元素必定是根节点的值,因为序列没有重复的元素,因此中序遍历中可以找到相同的这个元素,而我们又知道中序遍历中根节点将二叉树分成了左右子树两个部分,如下图所示:

图片说明

我们可以发现,数字1是根节点,并将二叉树分成了(247)和(3568)两棵子树,而子树的的根也是相应前序序列的首位,比如左子树的根是数字2,右子树的根是数字3,这样我们就可以利用前序遍历序列找子树的根节点,利用中序遍历序列区分每个子树的节点数。

具体做法:

  • step 1:先根据前序遍历第一个点建立根节点。
  • step 2:然后遍历中序遍历找到根节点在数组中的位置。
  • step 3:再按照子树的节点数将两个遍历的序列分割成子数组,将子数组送入函数建立子树。
  • step 4:直到子树的序列长度为0,结束递归。

Java实现代码:

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int n = pre.length;
        int m = vin.length;
        //每个遍历都不能为0
        if(n == 0 || m == 0) 
            return null;
        //构建根节点
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0; i < vin.length; i++){
            //找到中序遍历中的前序第一个元素
            if(pre[0] == vin[i]){ 
                //构建左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(vin, 0, i)); 
                //构建右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(vin, i + 1, vin.length));
                break;
            }
        }
        return root;
    }
}

C++实现代码:

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int n = pre.size();
        int m = vin.size();
        //每个遍历都不能为0
        if(n == 0 || m == 0) 
            return NULL;
        //构建根节点
        TreeNode *root = new TreeNode(pre[0]); 
        for(int i = 0; i < vin.size(); i++){
            //找到中序遍历中的前序第一个元素
            if(pre[0] == vin[i]){ 
                //左子树的前序遍历
                vector<int> leftpre(pre.begin() + 1, pre.begin() + i + 1);  
                //左子树的中序遍历
                vector<int> leftvin(vin.begin(), vin.begin() + i); 
                //构建左子树
                root->left = reConstructBinaryTree(leftpre, leftvin); 
                //右子树的前序遍历
                vector<int> rightpre(pre.begin() + i + 1, pre.end()); 
                //右子树的中序遍历
                vector<int> rightvin(vin.begin() + i + 1, vin.end()); 
                //构建右子树
                root->right = reConstructBinaryTree(rightpre, rightvin); 
                break;
            }
        }
        return root;
    }
};

Python实现代码

class Solution:
    def reConstructBinaryTree(self , pre: List[int], vin: List[int]) -> TreeNode:
        n = len(pre)
        m = len(vin)
        # 每个遍历都不能为0
        if n == 0 or m == 0: 
            return None
        # 构建根节点
        root = TreeNode(pre[0]) 
        for i in range(len(vin)):
            # 找到中序遍历中的前序第一个元素
            if pre[0] == vin[i]: 
                # 左子树的前序遍历
                leftpre = pre[1:i+1] 
                # 左子树的中序遍历
                leftvin = vin[:i] 
                # 构建左子树
                root.left = self.reConstructBinaryTree(leftpre, leftvin) 
                # 右子树的前序遍历
                rightpre = pre[i+1:] 
                # 右子树的中序遍历
                rightvin = vin[i+1:] 
                # 构建右子树
                root.right = self.reConstructBinaryTree(rightpre, rightvin) 
                break
        return root

复杂度分析:

  • 时间复杂度:O(n)O(n),其中nn为数组长度,即二叉树的节点数,构建每个节点进一次递归,递归中所有的循环加起来一共nn
  • 空间复杂度:O(n)O(n),递归栈最大深度不超过nn,辅助数组长度也不超过nn,重建的二叉树空间属于必要空间,不属于辅助空间
方法二:栈(思路扩展)

知识点:栈 栈是一种仅支持在表尾进行插入和删除操作的线性表,这一端被称为栈顶,另一端被称为栈底。元素入栈指的是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;元素出栈指的是从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

思路:

除了递归,我们也可以用类似非递归前序遍历的方式建立二叉树,利用栈辅助进行非递归,然后依次建立节点。

具体做法:

  • step 1:首先前序遍历第一个数字依然是根节点,并建立栈辅助遍历。
  • step 2:然后我们就开始判断,在前序遍历中相邻的两个数字必定是只有两种情况:要么前序后一个是前一个的左节点;要么前序后一个是前一个的右节点或者其祖先的右节点。
  • step 3:我们可以同时顺序遍历pre和vin两个序列,判断是否是左节点,如果是左节点则不断向左深入,用栈记录祖先,如果不是需要弹出栈回到相应的祖先,然后进入右子树,整个过程类似非递归前序遍历。

图示:

图片说明

Java实现代码:

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int n = pre.length;
        int m = vin.length;
        //每个遍历都不能为0
        if(n == 0 || m == 0) 
            return null;
        Stack<TreeNode> s = new Stack<TreeNode>();
        //首先建立前序第一个即根节点
        TreeNode root = new TreeNode(pre[0]); 
        TreeNode cur = root;
        for(int i = 1, j = 0; i < n; i++){
            //要么旁边这个是它的左节点
            if(cur.val != vin[j]){ 
                cur.left = new TreeNode(pre[i]);
                s.push(cur);
                //要么旁边这个是它的右节点,或者祖先的右节点
                cur = cur.left; 
            }else{
                j++;
                //弹出到符合的祖先
                while(!s.isEmpty() && s.peek().val == vin[j]){
                    cur = s.pop();
                    j++;
                }
                //添加右节点
                cur.right = new TreeNode(pre[i]); 
                cur = cur.right;
            }
        }
        return root;
    }
}

C++实现代码:

class Solution {
public:
    TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
        int n = pre.size();
        int m = vin.size();
        //每个遍历都不能为0
        if(n == 0 || m == 0) 
            return NULL;
        stack<TreeNode*> s;
        //首先建立前序第一个即根节点
        TreeNode *root = new TreeNode(pre[0]); 
        TreeNode *cur = root;
        for(int i = 1, j = 0; i < n; i++){
            //要么旁边这个是它的左节点
            if(cur->val != vin[j]){ 
                cur->left = new TreeNode(pre[i]);
                s.push(cur);
                //要么旁边这个是它的右节点,或者祖先的右节点
                cur = cur->left; 
            }else{
                j++;
                //弹出到符合的祖先
                while(!s.empty() && s.top()->val == vin[j]){ 
                    cur = s.top();
                    s.pop();
                    j++;
                }
                //添加右节点
                cur->right = new TreeNode(pre[i]); 
                cur = cur->right;
            }
        }
        return root;
    }
};

Python实现代码

class Solution:
    def reConstructBinaryTree(self , pre: List[int], vin: List[int]) -> TreeNode:
        n = len(pre)
        m = len(vin)
        # 每个遍历都不能为0
        if n == 0 or m == 0: 
            return None
        s = []
        # 首先建立前序第一个即根节点
        root = TreeNode(pre[0]) 
        cur = root
        j = 0
        for i in range(1, n):
            # 要么旁边这个是它的左节点
            if cur.val != vin[j]: 
                cur.left = TreeNode(pre[i])
                s.append(cur)
                # 要么旁边这个是它的右节点,或者祖先的右节点
                cur = cur.left 
            else:
                j += 1
                # 弹出到符合的祖先
                while s and s[-1].val == vin[j]: 
                    cur = s[-1]
                    s.pop()
                    j += 1
                # 添加右节点
                cur.right = TreeNode(pre[i]) 
                cur = cur.right
        return root

复杂度分析:

  • 时间复杂度:O(n)O(n),其中nn为数组长度,即二叉树的节点数,遍历一次数组,弹出栈的循环最多进行nn
  • 空间复杂度:O(n)O(n),栈空间最大深度为nn,重建的二叉树空间属于必要空间,不属于辅助空间