力扣-根据前序和后序遍历构造二叉树(java)-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣-根据前序和后序遍历构造二叉树(java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

leetcode 889 题（中等）

原题链接：
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/

题目描述：
给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有无重复值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
如果存在多个答案，您可以返回其中任何一个。

示例1：

输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

示例2：
输入: preorder = [1], postorder = [1]
输出: [1]

提示：
1 <= preorder.length <= 30
1 <= preorder[i] <= preorder.length
preorder 中所有值都不同
postorder.length == preorder.length
1 <= postorder[i] <= postorder.length
postorder 中所有值都不同
保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

解题思路

preorder = [1,2,4,5,3,6,7],
postorder = [4,5,2,6,7,3,1]
前序遍历头左右
后序遍历左右头
根据遍历顺序我们可以确定头节点，
然后在前序遍历中，头节点下一位置2 就是左节点起始位置，
通过2 可以在中序遍历中找到左子树的结束位置
左树确定好了，就可以确定右树了。

代码演示

/**
 * 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 constructFromPrePost(int[] preorder, int[] postorder) {
        int right = preorder.length - 1;
        return process(preorder,0,right,postorder,0,right);
    }
		/**
		* pre 前序遍历数组
		* ps 前序遍历起始位置
		* pe 结束位置
		* pos  后序遍历数组
		* hs 后序的起始位置
		* he 后序的结束位置
		*
		*/
    public TreeNode process(int[]pre,int ps,int pe,int[]pos,int hs,int he){
    	//base case 处理越界
        if(ps > pe || hs > he){
            return null;
        }
        //base case 相等时直接返回。
        if(ps == pe){
           return  new TreeNode(pre[ps]);
       }
       //直接先拿到头节点
        TreeNode root = new TreeNode(pre[ps]);
        //前序遍历中头节点下一个节点是左节点，直接拿到值
        int leftVal = pre[ps+1];
        //记录左节点在后序遍历中的位置
        int index = 0;
        //根据值比较 确定位置
        for(int i = hs;i <= he;i++){
            if(pos[i] == leftVal){
                index = i;
                break;
            }
        }
        //计算出左子树的节点数
        int leftSize = index - hs + 1;
        //构造左子树
        root.left = process(pre,ps+1,ps+leftSize,pos,hs,hs+leftSize-1);
        //构造右子树
        root.right = process(pre,ps+leftSize+1,pe,pos,index+1,he-1);
        return root;

    }
}