Hana_33 2022-04-29 17:13 采纳率: 63.6%
浏览 22
已结题

通过后续遍历和中序遍历得到二叉树

后序遍历:CFEGDBJLKIHA
后序遍历:CBEFDGAJIKLH

  • 写回答

1条回答 默认 最新

  • 不会长胖的斜杠 后端领域新星创作者 2022-04-29 17:19
    关注

    编程实现?可以参考

    package com.renxia;
    
    import sun.reflect.generics.tree.Tree;
    
    import java.util.HashMap;
    import java.util.Map;
    
    public class oneZeroSix {
        private static Map<Integer, Integer> inMap;
    
        public static class TreeNode{
            int val;
            TreeNode left;
            TreeNode right;
    
            public TreeNode(int val){
                this.val = val;
            }
        }
    
        public  static TreeNode myBuildTree(int[] inorder, int[] postorder, int istart, int iend, int pstart, int pend){
            if(pstart > pend)
                return null;
    
            int post_root =  pend;
            int in_root = inMap.get(postorder[post_root]);
            int num = in_root - istart;
    
            TreeNode root = new TreeNode(postorder[post_root]);
    
            root.left = myBuildTree(inorder, postorder, istart, in_root-1, pstart, pstart+num-1);
            root.right = myBuildTree(inorder, postorder, in_root+1, iend, pstart+num, pend-1);
            return root;
        }
    
        public static TreeNode buildTree(int[] inorder, int[] postorder){
            int n = inorder.length;
            inMap = new HashMap<>();
            for(int i=0; i < n; i++){
                inMap.put(inorder[i], i);
            }
            return myBuildTree(inorder, postorder, 0, n-1, 0, n-1);
        }
    
        public static void preOrder(TreeNode root){
            if(root == null)
                return;
            System.out.print(root.val + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    
        public static void main(String[] args) {
            int[] inorder = new int[]{9, 3, 15, 20, 7};
            int[] postorder = new int[]{9, 15, 7, 20, 3};
            TreeNode root = buildTree(inorder, postorder);
            preOrder(root);
        }
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录

报告相同问题?

问题事件

  • 系统已结题 5月13日
  • 已采纳回答 5月5日
  • 创建了问题 4月29日

悬赏问题

  • ¥15 Bibtex4Word 引用中文文献
  • ¥20 用opencv c/c++ 转换成灰度图,然后做一下直方图均衡,输出mp4文件
  • ¥20 matlab中的双层数值积分
  • ¥50 服务器打印水晶报表问题
  • ¥30 gradle环境下javafx项目如何使用druid连接池
  • ¥15 服务器打印水晶报表问题
  • ¥18 深度学习tensorflow1,ssdv1,coco数据集训练一个模型
  • ¥100 关于注册表摄像头和麦克风的问题
  • ¥30 代码本地运行正常,但是TOMCAT部署时闪退
  • ¥15 关于#python#的问题