欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指 Offer 07. 重建二叉树——【前中序】和【中后序】重建二叉树的递归思路详解

程序员文章站 2022-07-15 19:56:23
...

一、题目

二、分析

  • [首先不考虑代码,如何根据前序中序将二叉树还原]

    • 前序遍历的特点: 节点按照 [根 | 左 | 右] ; 后序 :[根 | 左 | 右] 排序
    • 根据以上特点,按照以下顺序 可以 还原出二叉树
      • 1. 前序数组的首个元素即为根节点root的值
      • 2. 在中序数组中找到根节点root的索引,此时中序划分为:[左子树|根节点|右子树]
      • 3.根据中序数组的左右子树的数量,可以将前序划分为:[根节点|左子树|右子树]
      • 4. 至此,我们可以确定三个节点的关系:树的根节点、左子树根节点、右子树根节点(即前序遍历中左(右)子树的首个元素)
      • 5. 根据子树特点,我们可以通过1,2,3 同样的方法对左(右)子树进行划分,每轮可确认三个节点的关系 。此递推性质让我们联想到用 递归方法 处理。
  • [如何递归?递归详解]

    • 地推参数: 前序遍历中根节点的索引pre_root、中序数组遍历左边界in_left、中序数组遍历右边界in_right。
    • 终止条件: 当 in_left > in_right ,子树中序遍历为空,说明已经越过叶子节点,此时返回 null
    • 递归工作:
      • 1. 建立根节点root: root值为前序遍历pre_root的节点值。
      • 2. 搜索根节点root 在中序遍历的索引i:为了提升搜索效率,本题解使用哈希表 预存储中序遍历的值与索引的映射关系,每次搜索的时间复杂度为 O(1)。
      • 3. 建立根节点root的左子树 和 右子树:开启递归recur() 递归下一层
        • 左子树:根节点索引为 pre_root + 1; 中序数组遍历左右边界:in_left 、i-1
        • 右子树:根节点索引为:pre_root + i - in_left + 1 (根节点索引+左子树的长度(i-in_left)+1);中序遍历的左右边界分别为 i + 1 和 in_right。
      • 4. 返回值:root 含义是当前递归层级建立的根节点 root 为上一递归层级的根节点的左或右子节点
  • [代码优化]

    • 为了减少代码的冗余 和提高代码性能。做了两个处理
      • 1.用hashmap 存储中序遍历数组, 便于搜索根节点在中序数组的索引
      • 2.创建类变量po[] 储存前序数组,便于创建root节点。
        hashmap 和 po[] 都是类变量。 如果不用类变量,需要在递归函数参数添加前序和中序数组

三、题解

class Solution {
        HashMap<Integer,Integer> map =  new  HashMap<Integer,Integer>();
        int[] po;
        
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            //存储中序
            for(int i = 0; i < inorder.length; i++){
                map.put(inorder[i],i);
            }
            //存储前序
            po = preorder;

            //递归
            return recur(0,0,inorder.length-1);
       }

       TreeNode recur(int pre_root, int in_left, int in_right){
           //递归终止条件
           if(in_left > in_right) return null;

           //创建根节点
           TreeNode root = new TreeNode(po[pre_root]);          
           //获取根节点在中序数组的索引i
           int i = map.get(po[pre_root]);

           //递归创建左右子树 *中序遍历的左右子树数量
           root.left = recur(pre_root+1, in_left, i-1);
           root.right = recur(pre_root+i-in_left+1, i+1, in_right); 

           //返回结果
           return root;
       }
}

四、复杂度分析

  • 时间复杂度 O(N) : N 为树的节点数量。初始化 HashMap 需遍历 inorder ,占用 O(N) ;递归共建立 N 个节点,每层递归中的节点建立、搜索操作占用 O(1) ,因此递归占用 O(N)。(最差情况为所有子树只有左节点,树退化为链表,此时递归深度 O(N) ;平均情况下递归深度 O(log2 N)。

  • 空间复杂度 O(N) : HashMap 使用 O(N) 额外空间;递归操作中系统需使用 O(N) 额外空间。

注:解题思路源于大佬 jyd 在Leetcode的题解:面试题07. 重建二叉树(递归法,清晰图解)

五、扩展:从中序与后序遍历序列构造二叉树

  • 题目106. 从中序与后序遍历序列构造二叉树
    剑指 Offer 07. 重建二叉树——【前中序】和【中后序】重建二叉树的递归思路详解

  • 分析
    解题思路与 前序后中序几乎一样。只需要注意 后序遍历数组,最后一个数才是根节点的值。还需要注意递归左右子树时,参数的计算。详情见代码
    另外,只有前序和后序的数组无法重建树,因为无法确定树的结构,比如前序[1,2] 后序[2,1]可以得到两种不同的树的结构。

  • 题解

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        HashMap<Integer, Integer> map = new HashMap();
        int po[]; //存后序
    
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            //存储中序
            for(int i  = 0; i < inorder.length; i++){
                map.put(inorder[i],i);
            }
            //存储后序
            po = postorder;
    
            //递归
            return recur(postorder.length-1,0,postorder.length-1);//注意参入参数
    
        }
        private TreeNode recur(int post_root, int in_left, int  in_right){
            //异常处理
            if(in_left > in_right) return null;
    
            //创建根结点 。 后序数组的最后一个数是根节点的值
            TreeNode root = new TreeNode(po[post_root]);
    
            //获取根节点 在中序遍历数组的下标i
            int i = map.get(po[post_root]);
    
            //递归左右子树 根据中序数组根节点root的索引i 划分的左右子树数量 
            /* 后序 左右根     
               
                右子树:根节点 post_root 是后序最后一个节点。
                     post_root+1是右子树的根节点。
                     中序遍历左右边界: i+1  和 in_right 
                左子树:根节点 post_root - 右子树的数量(in_right -i) -1
                     中序遍历的左右边界:int_left 和 i-1
            */
            root.right = recur(post_root-1, i+1, in_right);//注意传入的参数
    		//递归顺序可以修改
            root.left = recur(post_root-in_right+i-1, in_left, i-1);//注意传入的参数
    		
    		//返回值
            return root;
    
        }
    }