小白力扣算法题day07-二叉树

想不出来，看答案做的，利用递归和哈希表想不到。

class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { // 第一步：创建一个哈希表（字典），用来快速找到中序遍历中某个值的位置 // 为什么要这样做？因为在中序遍历中找根节点的位置时，如果每次都遍历数组，会很慢 // 用哈希表可以在 O(1) 时间内找到位置 Map<Integer, Integer> inorderMap = new HashMap<>(); // 遍历中序遍历数组，把每个值和它的索引存到哈希表中 // 例如 inorder = [9,3,15,20,7] // 那么 map 里就会存：{9:0, 3:1, 15:2, 20:3, 7:4} for (int i = 0; i < inorder.length; i++) { inorderMap.put(inorder[i], i); } // 调用递归函数，开始构建二叉树 // 参数说明： // preorder: 前序遍历数组 // 0: 前序遍历的起始索引 // preorder.length - 1: 前序遍历的结束索引 // inorder: 中序遍历数组 // 0: 中序遍历的起始索引 // inorder.length - 1: 中序遍历的结束索引 // inorderMap: 哈希表，用来快速定位根节点在中序遍历中的位置 return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inorderMap); } private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd, Map<Integer, Integer> inorderMap) { // 递归终止条件：如果起始索引大于结束索引，说明这个区间没有节点了 // 例如左子树没有节点时，inStart > inEnd，返回 null if (preStart > preEnd || inStart > inEnd) { return null; } // 前序遍历的第一个节点就是当前子树的根节点 // 例如 preorder = [3,9,20,15,7]，第一个元素 3 就是根节点 int rootVal = preorder[preStart]; TreeNode root = new TreeNode(rootVal); // 创建根节点 // 在中序遍历中找到根节点的位置 // 例如 inorder = [9,3,15,20,7]，根节点 3 在索引 1 的位置 int rootIndexInorder = inorderMap.get(rootVal); // 计算左子树的节点个数 // 左子树的节点数 = 根节点在中序遍历中的位置 - 中序遍历的起始位置 // 例如：inStart=0, rootIndexInorder=1，那么左子树有 1-0=1 个节点（就是 9） int leftSize = rootIndexInorder - inStart; // ========== 构建左子树 ========== // 左子树的前序遍历范围： // 起始索引：preStart + 1（跳过当前的根节点） // 结束索引：preStart + leftSize（从前序中取 leftSize 个节点给左子树） // 左子树的中序遍历范围： // 起始索引：inStart // 结束索引：rootIndexInorder - 1（根节点左边都是左子树的节点） root.left = build(preorder, preStart + 1, preStart + leftSize, inorder, inStart, rootIndexInorder - 1, inorderMap); // ========== 构建右子树 ========== // 右子树的前序遍历范围： // 起始索引：preStart + leftSize + 1（跳过左子树的所有节点） // 结束索引：preEnd // 右子树的中序遍历范围： // 起始索引：rootIndexInorder + 1（根节点右边都是右子树的节点） // 结束索引：inEnd root.right = build(preorder, preStart + leftSize + 1, preEnd, inorder, rootIndexInorder + 1, inEnd, inorderMap); // 返回构建好的根节点 return root; } }

class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { Map<Integer,Integer>map=new HashMap<>(); for (int i=0;i<inorder.length;i++){ map.put(inorder[i],i); } return build(inorder,0,inorder.length-1, postorder,0,postorder.length-1,map); } private TreeNode build(int[] inorder,int inStart,int inEnd, int[] postorder,int poStart,int poEnd,Map<Integer,Integer>map){ if(inStart>inEnd||poStart>poEnd){ return null; } int rootVal=postorder[poEnd]; TreeNode root=new TreeNode(rootVal); int rootInorderIndex=map.get(rootVal); int leftSize=rootInorderIndex-inStart; root.left=build(inorder,inStart,rootInorderIndex-1, postorder,poStart,poStart+leftSize-1,map); root.right=build(inorder,rootInorderIndex+1,inEnd, postorder,poStart+leftSize,poEnd-1,map); return root; } }

相同原理加以巩固。

class Solution { public boolean hasPathSum(TreeNode root, int targetSum) { if(root==null)return false; if(root.left==null&&root.right==null){ return targetSum== root.val; } int remain=targetSum-root.val; return hasPathSum(root.left,remain)||hasPathSum(root.right,remain); } }

递归的应用