思路(模拟):
每次在前序遍历确定一个根节点,然后在中序遍历中查找到这个节点的位置,中序遍历中该节点左侧的节点为该节点的左子树,该节点右侧的节点为右子树。
用哈希表可将查找节点位置的操作变为O(1)
---------------------------------------------------解法---------------------------------------------------:
/** * 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 { Map<Integer,Integer> hashmap = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { int n = preorder.length; // 用哈希表映射中序遍历每个节点的位置 for(int i = 0;i < n;i++) hashmap.put(inorder[i],i); return bulid(preorder,inorder,0,n - 1,0,n - 1); } public TreeNode bulid(int[] preorder,int[] inorder,int pl,int pr,int il,int ir){ if(pl > pr || il > ir) return null; // 通过前序遍历找到根节点 int t = preorder[pl]; // 建立根节点 TreeNode root = new TreeNode(t); // 找到中序遍历中该根节点的位置 int k = hashmap.get(t); // 求出左子树长度 int len = k - il; // 递归构建左子树 root.left = bulid(preorder,inorder,pl+1,pl + 1 + k - 1 - il,il,k - 1); // 递归构建右子树 root.right = bulid(preorder,inorder,pl + 1 + k - 1 - il + 1,pr,k + 1,ir); return root; } }
可能存在的问题: