牛客题霸NC12重建二叉树Java题解

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了牛客题霸NC12重建二叉树Java题解，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1064字，纯文字阅读大概需要2分钟。

内容图文

牛客题霸NC12重建二叉树Java题解

https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=117&&tqId=35043&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking

方法：递归
解题思路：在前序遍历中找根节点，可将中序遍历划分为左、根、右。根据中序遍历中的左、右子树的节点数量，可以将前序遍历划分为根、左、右。

import java.util.*;
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
 
    int[] po;
    HashMap<Integer,Integer> map = new HashMap<>();
 
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        po = pre;
        for(int i=0;i<in.length;i++){
            map.put(in[i],i);
        }
        return recur(0,0,in.length-1);
    }
 
     private TreeNode recur(int pre_root,int in_left,int in_right){
 
        if(in_left>in_right){
            return null;
        }
 
        TreeNode root = new TreeNode(po[pre_root]);  // 建立根节点
 
        //获取根节点在中序中的索引
        int i = map.get(po[pre_root]);
 
        root.left = recur(pre_root+1,in_left,i-1);  //中序
        root.right = recur(pre_root+(i-in_left)+1,i+1,in_right); //中序
 
        return root; 
    }
}

 

内容总结

以上是互联网集市为您收集整理的牛客题霸NC12重建二叉树Java题解全部内容，希望文章能够帮你解决牛客题霸NC12重建二叉树Java题解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---