「剑指Offer」Day20:分治算法(中等)
剑指 Offer 07. 重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果,请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]🔗链接:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
思路
题解:NC12:重建二叉树
代码实现一
调用Arrays.copyOfRange()方法拆分数组
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { int length = preorder.length; //两个遍历序列的长度是一样的 if(length == 0){ return null; } TreeNode root = new TreeNode(preorder[0]); //当前前序遍历序列的第一个元素即为根节点 for(int i = 0; i < inorder.length; i++){ //遍历查找根节点在中序遍历序列中的位置,根据该位置拆分两个序列,分别对应当前根节点的左右子树 if(inorder[i] == preorder[0]){ root.left = buildTree(Arrays.copyOfRange(preorder, 1, i+1), Arrays.copyOfRange(inorder, 0, i)); root.right = buildTree(Arrays.copyOfRange(preorder, i+1, preorder.length), Arrays.copyOfRange(inorder, i+1, inorder.length)); return root; } } return root; } }
代码实现二
题目中说输入的前序遍历和中序遍历的结果中都不含重复的数字,因此可以使用哈希表维护中序遍历序列中节点值与下标之间的映射,通过下标完成拆分
class Solution { //需根据前序遍历序列的值确定当前的根节点 int[] preorder; HashMap<Integer, Integer> dic = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; for(int i = 0; i < inorder.length; i++){ dic.put(inorder[i], i); } return recur(0, 0, inorder.length - 1); } TreeNode recur(int root, int left, int right) { if(left > right) return null; // 递归终止 TreeNode node = new TreeNode(preorder[root]); // 建立根节点 int i = dic.get(preorder[root]); // 划分根节点、左子树、右子树 node.left = recur(root + 1, left, i - 1); // 开启左子树递归 node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归 return node; // 回溯返回根节点 } }
剑指 Offer 16. 数值的整数次方
题目描述
实现 pow(x, n) ,即计算 x 的 n 次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。
输入:x = 2.00000, n = 10 输出:1024.00000 输入:x = 2.00000, n = -2 输出:0.25000 解释:2-2 = 1/22 = 1/4 = 0.25🔗题目链接:https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/
思路
快速幂
代码实现
class Solution { public double myPow(double x, int n) { if(x == 0) return 0; long b = n; double res = 1.0; if(b < 0) { x = 1 / x; b = -b; } while(b > 0) { if((b & 1) == 1) res *= x; x *= x; b >>= 1; } return res; } }
剑指 Offer 33. 二叉搜索树的后序遍历序列
题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
🔗题目链接:https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/
思路
方法一:递归
class Solution { public boolean verifyPostorder(int[] postorder) { return recur(postorder, 0, postorder.length - 1); } boolean recur(int[] postorder, int i, int j) { if(i >= j) return true; int p = i; while(postorder[p] < postorder[j]) p++; int m = p; while(postorder[p] > postorder[j]) p++; return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1); } }