【LeetCode】106. 从中序与后序遍历序列构造二叉树


1.问题

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

示例 1

""

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]

示例 2

输入:inorder = [-1], postorder = [-1]
输出:[-1]

提示:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 3000
  • inorder 和 postorder 都由 不同 的值组成
  • postorder 中每一个值都在 inorder 中
  • inorder 保证是树的中序遍历
  • postorder 保证是树的后序遍历

2.解题思路

可以借鉴【LeetCode】105. 从前序与中序遍历序列构造二叉树的思想。
同样需要将中序的值-索引先存储。
第一个节点(根节点)在后序序列中为postorder[postorder.length-1],令其二叉树节点为root,index为其值在中序序列的索引,则root.left在中序序列的范围:[inStart, index-1],在后序序列的范围:[postStart, postStart+index-inStart-1];而root.right在中序序列的范围:[index+1, inEnd],在后序序列的范围:[postStart+index-inStart, postEnd-1]. 如图所示:

""

其中leftSize为 index-inStart.

""

3.代码

/**
 * 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 {
    private HashMap<Integer, Integer> elementIndexMap=new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(0==inorder.length){
            return null;
        }
        //首次先遍历下中序,记录各个元素的位置,方便定位后序数组中的元素在中序数据中的位置,区分左右子树
        if(elementIndexMap.size()==0){
            for(int i=0;i<inorder.length;i++){
                elementIndexMap.put(inorder[i],i);
            }
        }
        //以中序序列为主,将根节点从后序序列最后一个节点取出,确定其在中序中的定位,然后分为前后两节点树,根节点前为左子树,其后为右子树
        return buildTree2(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
    }

    /**
        inStart 中序开始下标
        inEnd 中序结束下标
        postEnd 后序结束下标(根节点)
     */
    private TreeNode buildTree2(int[] inorder,int inStart,int inEnd,int[] postorder,int postStart, int postEnd){
        if(inStart>inEnd){
            return null;
        }
        int rootValue=postorder[postEnd];
        TreeNode root=new TreeNode(rootValue);
        int index=elementIndexMap.get(rootValue);
        int offset=index-inStart;
        //左子树-中序数组 is = inStart, ie = index - 1
        //左子树-后序数组 ps = postStart, pe = postStart + offset - 1
        root.left=buildTree2(inorder,inStart, index-1, postorder, postStart, postStart+offset-1);
        //右子树-中序数组 is = index+1, ie = inEnd
        //右子树-后序数组 ps = postStart+offset, pe = postEnd - 1
        root.right=buildTree2(inorder,index+1,inEnd,postorder, postStart+offset,postEnd-1);
        return root;
    }
}

文章作者: Kezade
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Kezade !
评论
  目录