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

Java资料网推荐从中序与后序遍历序列构造二叉树-106这篇文章给大家，欢迎收藏Java资料网享受知识的乐趣

题目描述

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

解题思路

这题我们的思路还是递归去构造我们的二叉树，首先题目给出二叉树的中序遍历和后序遍历，由后序遍历我们可以确定我们当前这颗二叉树的根节点，然后转到中序遍历我们可以根据根节点判断哪些节点是左孩子，哪些节点是右孩子，然后再去后序遍历中判断左孩子节点的后序遍历顺序和右孩子节点的后序遍历顺序，然后我们递归一层一层往下去构建我们的二叉树就行了

代码实例

import java.util.*;
class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder.length==0){
            return null;
        }
        int rootValue=postorder[postorder.length-1];
        TreeNode root=new TreeNode(rootValue);

        if(postorder.length==1){
            return root;
        }
       
        int rootIndex;
        for(rootIndex=0;rootIndex<inorder.length;rootIndex++){
            if(inorder[rootIndex]==rootValue){
                break;
            }
        }
		
        //确定中序中左孩子节点的中序遍历顺序
        int[] leftzhongxu=Arrays.copyOfRange(inorder,0,rootIndex);
        //确定中序右左孩子节点的中序遍历顺序
        int[] rightzhongxu=Arrays.copyOfRange(inorder,rootIndex+1,inorder.length);

        //确定后序中左孩子节点的后序遍历顺序
        int[] lefthouxu=Arrays.copyOfRange(postorder,0,rootIndex);
        //确定后序中右孩子节点的后序遍历顺序
        int[] righthouxu=Arrays.copyOfRange(postorder,rootIndex,postorder.length-1);
		
        //递归去构建根节点的左右子树
        root.left=buildTree(leftzhongxu,lefthouxu);
        root.right=buildTree(rightzhongxu,righthouxu);
        
       	//返回结果
        return root;
    }
}

文章来源:https://www.cnblogs.com/dfj-blog/p/18463233
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！