Leetcode剑指Offer刷题

Leetcode剑指Offer刷题指南：

Leetcode剑指Offer刷题-学习计划目录_DEGv587的博客-CSDN博客

剑指 Offer 07、重建二叉树 

题目信息：前序遍历和中序遍历的结果中都不含重复的数字

解法：分治思想

class Solution { int[] preorder;//保留的先序遍历 HashMap map = new HashMap<>();//标记中序遍历 public TreeNode buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; for (int i = 0; i < inorder.length; ++i) { map.put(inorder[i], i); } return func(0, 0, inorder.length - 1); } private TreeNode func(int root, int left, int right) { if (left > right) return null; TreeNode node = new TreeNode(preorder[root]);//建立根节点 int i = map.get(preorder[root]);//划分根节点，左右子树 node.left = func(root + 1, left, i - 1);//左子树递归 node.right = func(root + i - left + 1, i + 1, right);//右子树递归 return node; }}

剑指 Offer 16、数值的整数次方

解法：快速幂

逐步分解

偶数变换，奇数多一个进行处理

2^10 = (2^5) * (2^5) = (4^2) * (4^2) * 4 = 16 * 16 * 4

class Solution { public double myPow(double x, int n) { if (x == 0) return 0; long b = n;//防止越界 double ret = 1.0; if (b < 0) { x = 1 / x; b = -b; } while (b > 0) { if ((b & 1) == 1) { //处理奇数 ret *= x; } x *= x; b >>= 1; } return ret; }}

剑指 Offer 33、二叉搜索树的后序遍历序列

解法一：递归分治

遍历后序遍历的 [i, j] 区间元素，寻找 第一个大于根节点 的节点,索引记为 m

postorder[j]则是根节点

左子树区间 [i, m - 1] 内的所有节点都应 < postorder[j]

右子树区间 [m, j-1] 内的所有节点都应 > postorder[j]

class Solution { public boolean verifyPostorder(int[] postorder) { return verifyHelp(postorder, 0, postorder.length - 1); } private boolean verifyHelp(int[] postorder, int i, int j) { if (i >= j) return true; int p = i; while (postorder[p] < postorder[j]) { //比根节点小就继续向后走 p++; } //遇到第一个大于根节点的值，记录为m int m = p; while (postorder[p] > postorder[j]) { //比根节点大就继续向后走 p++; } //递归分治左子树和右子树 return p == j && verifyHelp(postorder, i, m - 1) && verifyHelp(postorder, m, j - 1); }}

解法二：辅助单调栈

class Solution { public boolean verifyPostorder(int[] postorder) { Stack stack = new Stack<>(); int root = Integer.MAX_VALUE; for (int i = postorder.length - 1; i >= 0; --i) { //如果当前节点比根节点还大，则直接返回false if (postorder[i] > root) return false; while (!stack.isEmpty() && stack.peek() > postorder[i]) { //去找当前节点的父节点 root = stack.pop(); } stack.add(postorder[i]); } return true; }}