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

题目

方法一：递归构建

1. 后序遍历用于确定根节点是哪个
2. 中序遍历用于根据后序遍历的根确定出左右子树的范围
3. 可以提前将中序遍历值和下标存入map，方便后续根据后序遍历的根去中序遍历寻找根，然后区分左右子树，进行递归

只需确定三个变量即可
int postend 后序遍历根的位置
int inbegin前序遍历子树的范围（根据后序的根区分）左边界
int inend前序遍历子树的范围（根据后序的根区分）右边界

• 后序遍历根的位置
• 前序遍历子树的范围（根据后序的根区分）左边界与右边界
  递归结束条件为 前序遍历的左边界大于了右边界

 public TreeNode MakebuildTree(int postend,int inbegin,int inend ){
        if(inbegin > inend ){
            return null;
        }
1
2
3
4

class Solution {
    Map<Integer,Integer> map = new HashMap<>();//记录中序遍历中数的索引位置，方便在后续遍历中找到根后快速切割左右子树
    int[] postNumber = null;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for(int i = 0 ;  i<inorder.length;i++) map.put(inorder[i],i);
        this.postNumber = postorder;
        return MakebuildTree(postorder.length-1,0,inorder.length-1);
    }
    public TreeNode MakebuildTree(int postend,int inbegin,int inend ){
        if(inbegin > inend ){
            return null;
        }
        int inrootindex = map.get(postNumber[postend]);//根据后序最后一个节点（根）确定中序遍历的根  后面好做截断
        TreeNode root = new TreeNode(postNumber[postend]);//构建节点

        int rightTreeSize = inend - inrootindex;//得出右子树的数目  方便后面截断左右子树寻找孩子节点
        //构建子树的时候 一定要根据中序遍历的根节点去后序遍历中的根节点 这样才能确定下一次构建子树所需的根节点是哪个
        root.right = MakebuildTree(postend-1,inrootindex+1,inend);//构建右子树
        root.left = MakebuildTree(postend - rightTreeSize - 1, inbegin, inrootindex - 1);//构建左子树
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22