力扣(LeetCode)106. 从中序与后序遍历序列构造二叉树

一、目标

    给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

二、代码分析

总体代码：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    //声明map，因为后续涉及频繁索引操作，而数字无法根据数值直接返回索引，用一个map来存

    HashMap<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        //遍历数组，将数组中的值作为key，对应值的索引作为value，传入map中储存
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        //调取Get方法，该方法会返回创建的二叉树的根节点

        return Get(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    /*传入参数分别为inorder数组，当前选择的中序数组起始索引inBegin， 当前选择的中序数组                                                    
      终止索引inEnd，后序数组postorder，当前选择的后序数组起始索引postBegin，当前选择的                        
      后序数组终止索引postEnd，
    */

    public TreeNode Get(int[] inorder, int inBegin, int inEnd, int[] postorder, 
                        int postBegin, int postEnd)
        {

        //递归终止判断条件

        if(inBegin >= inEnd || postBegin >= postEnd){
            return null;
            }
        TreeNode root = new TreeNode();

        //拿到后序数组中最后一个元素在中序数组中的索引记为rootindex

        int rootindex = map.get(postorder[postEnd - 1]);

        //记录分割出来的左子树的中序遍历长度，下面用来在后序数组中根据这个长度分割

        int leftlength = rootindex - inBegin;

        //记录当前找出的子树的根节点

        root.val = inorder[rootindex];

        //递归对当前节点左右子节点调用Get，但注意进行区间的分割
        root.left = Get(inorder, inBegin, inBegin + leftlength, postorder, 
                        postBegin, postBegin + leftlength);
        root.right = Get(inorder, rootindex + 1, inEnd, postorder, 
                         postBegin + leftlength, postEnd - 1);
        return root;
    }
}

     用一个map来存中序数组的索引和数值，因为后序涉及从值获取索引

        map = new HashMap<>();
        //遍历数组，将数组中的值作为key，对应值的索引作为value，传入map中储存
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        //调取Get方法，该方法会返回创建的二叉树的根节点

 中序遍历顺序：左中右

 后序遍历顺序：左右中

  本方法整体思路为：
  先从后序数组中找到最后一个节点记为根节点(后序数组中找到最后一个节点一定是根节点)，储存这个节点，根据根节点对中序数组进行切割，分中左序列和中右序列，然后根据中左的长度对后序数组从头开始切割分成后左序列和后右序列，再次递归调取切割函数，左节点获取需要传入中左，后左，右节点获取需要传入中右，后右，终止条件为区间起点终点相同。

    /*传入参数分别为inorder数组，当前选择的中序数组起始索引inBegin， 当前选择的中序数组                                                    
      终止索引inEnd，后序数组postorder，当前选择的后序数组起始索引postBegin，当前选择的                        
      后序数组终止索引postEnd，
    */

    public TreeNode Get(int[] inorder, int inBegin, int inEnd, int[] postorder, 
                        int postBegin, int postEnd)
        {

        //递归终止判断条件

        if(inBegin >= inEnd || postBegin >= postEnd){
            return null;
            }
        TreeNode root = new TreeNode();

        //拿到后序数组中最后一个元素在中序数组中的索引记为rootindex

        int rootindex = map.get(postorder[postEnd - 1]);

        //记录分割出来的左子树的中序遍历长度，下面用来在后序数组中根据这个长度分割

        int leftlength = rootindex - inBegin;

        //记录当前找出的子树的根节点

        root.val = inorder[rootindex];

        //递归对当前节点左右子节点调用Get，但注意进行区间的分割
        root.left = Get(inorder, inBegin, inBegin + leftlength, postorder, 
                        postBegin, postBegin + leftlength);
        root.right = Get(inorder, rootindex + 1, inEnd, postorder, 
                         postBegin + leftlength, postEnd - 1);
        return root;
    }

  获取左节点时候传入区间为中左序列(inBegin, inBegin + leftlength)和后左序列(postBegin, postBegin + leftlength)

  获取右节点时候传入区间为中右序列(rootindex + 1, inEnd)和后右序列(postBegin + leftlength, postEnd - 1)

         //递归对当前节点左右子节点调用Get，但注意进行区间的分割
        root.left = Get(inorder, inBegin, inBegin + leftlength, postorder, 
                        postBegin, postBegin + leftlength);
        root.right = Get(inorder, rootindex + 1, inEnd, postorder, 
                         postBegin + leftlength, postEnd - 1);

三、总结

  虽然是中等难度，但我觉得这道题不好写，可以作为按照特定规则递归法构造二叉树的经典题目来好好学习。