牛客题霸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; } }