leetcode刷题笔记-105. 从前序与中序遍历序列构造二叉树｜106. 从中序与后序遍历序列构

题目描述

105. 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

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

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

解题思路

• 前序遍历：根结点--左子结点--右子结点
• 中序遍历：左子结点--根结点--右子结点
• 后序遍历：左子结点--右子结点--根结点

这两道题目的思路是一样的。前序遍历，第一个节点就是跟节点，后续遍历最后一个节点是跟节点，中序遍历跟节点左右两侧是二叉树的左右子树。

就以105题目讲解，106题目相当于换了跟节点的位置，思路是一致的。105是前序遍历，所以，第一个就是跟节点，然后通过中序遍历就可以知道左右子树是哪几个元素，然后左子树和右子树在前序遍历中第一个又是跟节点，所以可以根据这个进行递归，不断的变换跟节点及前序遍历中的下标（对应左右子树的开始结束位置）

解题代码

105题解：

/**
 * 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 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //中序遍历放到map中做索引，加快查询速度
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length, inorder, 0, inorder.length, map);
    }

    public TreeNode build(int[] preorder,int pl, int ph, int[] inorder,int il,int ih,Map<Integer, Integer> map) {
        //结束条件
        if(pl >= ph) {
            return null;
        }
        //前序遍历，第一个就是跟节点
        int rootVal = preorder[pl];
        //在中序遍历中获取跟节点下标，然后就知道左右子树的开始和结束下标及对应数组长度
        int rootIndex = map.get(rootVal);
        TreeNode root = new TreeNode(rootVal);
        //计算左子树长度
        int leftLength = rootIndex - il;
        //递归调用左子树
        root.left = build(preorder, pl+1, pl+leftLength+1, inorder, il, rootIndex, map);
        //递归调用右子树
        root.right = build(preorder, pl+leftLength+1, ph, inorder, rootIndex+1, ih, map);
        return root;
    }
}

106题解：

/**
 * 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 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        //中序遍历放入map，作为索引，加快查询
        Map<Integer, Integer> map = new HashMap<>();
        for(int i=0;i<inorder.length;i++) {
            map.put(inorder[i], i);
        }
        return build(postorder,0, postorder.length,inorder,0,inorder.length,map);
    }

    public TreeNode build(int[] postorder,int pl,int ph,int[] inorder,int il,int ih,Map<Integer, Integer> map) {
        //结束条件
        if(pl >= ph) {
            return null;
        }
        //后序遍历最后一个元素是跟节点
        int rootVal = postorder[ph-1];
        //中序遍历跟节点位置，然后可以知道左右子树的下标及对应数组长度
        int rootIndex = map.get(rootVal);
        //计算右子树长度
        int rightLength = ih-rootIndex-1;
        TreeNode root = new TreeNode(rootVal);
        //递归左子树
        root.left = build(postorder, pl, ph-rightLength-1, inorder, il, rootIndex,map);
        //递归右子树
        root.right = build(postorder, ph-rightLength-1,ph-1,inorder,rootIndex+1,ih,map);
        return root;
    }
}