本文主要是介绍力扣剑指Offer 第20天 分治算法（中等）剑指 Offer 07. 重建二叉树 剑指 Offer 16. 数值的整数次方 剑指 Offer 33. 二叉搜索树的后序遍历序列，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

力扣剑指Offer 第20天 分治算法（中等）剑指 Offer 07. 重建二叉树 剑指 Offer 16. 数值的整数次方 剑指 Offer 33. 二叉搜索树的后序遍历序列

剑指 Offer 07. 重建二叉树

题目

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制：

0 <= 节点个数 <= 5000

题解

分治 二叉树遍历的性质

前序遍历列表：第一个元素永远是 【根节点 (root)】

中序遍历列表：根节点 (root)【左边】的所有元素都在根节点的【左分支】，【右边】的所有元素都在根节点的【右分支】

算法思路：

通过【前序遍历列表】确定【根节点 】

将【中序遍历列表】的节点分割成【左分支节点】和【右分支节点】

递归寻找【左分支节点】中的【根节点】和 【右分支节点】中的【根节点 】

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int[] preorder=null;
    private HashMap<Integer,Integer>map=null;
    private int pre=-1;
    private TreeNode divide(int l,int r){
        if(++pre>=preorder.length)return null;
        int in=map.get(preorder[pre]);
        TreeNode node=new TreeNode(preorder[pre]);
        // System.out.println(node.val+" in:"+in);
        if(l<in)node.left=dfs(l,in-1);
        if(r>in)node.right=dfs(in+1,r);
        return node;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0)return null;
        this.preorder=preorder;
        map=new HashMap<>();
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return divide(0,inorder.length-1);
    }
}

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

题目

实现pow(x, n) ，即计算 x 的 n 次幂函数（即，xⁿ）。不得使用库函数，同时不需要考虑大数问题。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：pow(2,-2) = pow(0.5,2) = 0.25

提示：

1. -100.0 < x < 100.0
2. -2³¹ <= n <= 2³¹-1
3. -10⁴ <= xⁿ <= 10⁴

题解

快速幂

边界：幂为0返回1

幂为奇数则将幂-1，结果乘以一个底数

幂为偶数则将幂除以2，底数平方

（相当于将原本的求复杂幂转换为求平方，将底数与幂做微妙的转换，使得幂一步步开平方急速降维）

本题虽然数据在int范围内，但是由于我们对幂的取反操作，使得当幂等于Integer.minValue时取反溢出发生错误！所以得开long！

递归实现

class Solution {
    private double pow(double x,long n){
        if(n==0L)return 1.0;
        if((n&1L)==1L)return pow(x,n-1L)*x;
        return pow(x*x,n/2L);
    }
    public double myPow(double x, int n) {
        if(n==0)return 1;
        if(x==0.0)return 0;
        long m=n;
        if(m<0){
            x=1.0/x;
            m=-m;
        }
        return pow(x,m);
    }
}

非递归实现

class Solution {
    public double myPow(double x, int n) {
        if(n==0)return 1;
        if(x==0.0)return 0;
        long m=n;
        if(m<0){
            x=1.0/x;
            m=-m;
        }
        double ans=1;
        while(true){
            if(m==0)break;
            if((m&1)==1){
                ans*=x;
                m--;
            }else{
                x*=x;
                m/=2L;
            }
        }
        return ans;
    }
}

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

题目

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

	 5
	/ \
   2   6
  / \
 1   3

示例 1：

输入: [1,6,3,2,5]
输出: false

示例 2：

输入: [1,3,2,6,5]
输出: true

提示：

数组长度 <= 1000

题解

分治

1. 二叉搜索树的性质：左子树的值小于根值，右子树的值大于根的值
2. 后序遍历：先递归搜索左子树，再递归搜索右子树，然后输出当前节点
3. 无重复值节点

从最右的节点（根节点）开始，将左边数组划分为左子树（小于根值）与右子树（大于根值）

（如果在划分时发现不符合条件则说明不是二叉搜索树 返回false）

边界：划分后的数组长度小于等于3时（任意3个元素都可以组成一个二叉搜索子树）

class Solution {
    private boolean divide(int[] postorder,int l,int r){
        // System.out.println("l:"+l+" r:"+r);
        if(r-l<=2)return true;
        int i=l,root=postorder[r];
        while(i<r&&postorder[i]<root)i++;//寻找右区域的左端
        int j=i;
        while(j<r&&postorder[j]>root)j++;//检测右区域是否符合条件（全部大于根）
        // System.out.println("i:"+i+" j:"+j);
        if(j!=r)return false;
        return divide(postorder,l,i-1)&&divide(postorder,i,r-1);
    }
    public boolean verifyPostorder(int[] postorder) {
        if(postorder.length<=2)return true;
        return divide(postorder,0,postorder.length-1);
    }
}

这篇关于力扣剑指Offer 第20天 分治算法（中等）剑指 Offer 07. 重建二叉树 剑指 Offer 16. 数值的整数次方 剑指 Offer 33. 二叉搜索树的后序遍历序列的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！