重建二叉树

medium 原题连接：重建二叉树

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

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

示例：

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

限制：

  1. 0 <= 节点个数 <= 5000

解题思路

  1. 先序遍历是指：根节点优先遍历，然后遍历左节点，再是右节点（根左右）；中序遍历是指：先遍历左节点，再遍历根节点，最后遍历右节点（左根右）
  2. 在没有单子树的前提下，对于先序遍历，根节点后一定跟着自己的左节点；对于中序遍历，根节点后一定跟着自己的右节点；且先序遍历第一位一定是总的根节点
  3. 先序遍历可以用于查找每一个子节点的根与左节点关系，而且是从第一个值开始查：数组存
  4. 中序遍历在知道某一个根节点时可以知道其根与右节点关系，但是需要提前找到根：Map存
  5. 实现：先序遍历找到一个根，确定左节点，依据这个根将中序遍历分为两个部分，确定右节点，组合节点
  6. 根据5得到的左右节点，将先序遍历数组分为两个部分：根 （左子树部分）（右子树部分），对此两个部分重复5，6直至不可分

Java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int[] preorders;
    HashMap<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorders = preorder;
        for(int i=0; i<inorder.length; i++){
            map.put(inorder[i],i);
        }
        return fun(0,0,inorder.length-1);
    }

    TreeNode fun(int root, int left, int right){
        if(left > right)return null;
        TreeNode node = new TreeNode(preorders[root]);
        int i = map.get(preorders[root]);    //获得根节点位置，划分左右子树
        node.left = fun(root+1, left, i-1);
        // 右节点在先序中的起始位置：当前位置 + 左子树数量 + 1
        node.right = fun(root+(i-left)+1, i+1, right);
        return node;
    }
}

数值的整数次方

medium 原题连接：数值的整数次方

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

示例：

输入：x = 2.00000, n = 10
输出：1024.00000
输入：x = 2.10000, n = 3
输出：9.26100
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

  1. -100.0 < x < 100.0
  2. -231 <= n <= 231-1
  3. -104 <= xn <= 104

解题思路

递归进阶版

  1. 统一正负次方的计算：如果n<0，将n设为-n，同时返回的值为 1/ans
  2. 暴力遍历会超时，需要使用递归乘方
  3. 1的任何次方都是1，任何数的0次方都是1

Java代码

class Solution {
    public double myPow(double x, int n) {
        long times = n;
        if(x == 1) return 1;
        return n >= 0 ? fun(x, times) : 1d/fun(x, times);
    }

    public double fun(double x, long n) {
        if(n == 0) return 1;
        double num = fun(x, n/2);
        return n%2==0 ? num*num : x * num * num;
    }
}

二叉搜索树的后序遍历序列

medium 原题连接：二叉搜索树的后序遍历序列

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

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

     5
    / \
   2   6
  / \
 1   3

示例：

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

提示：

  1. 数组长度 <= 1000

解题思路

后序遍历：先遍历左节点，再遍历右节点，最后遍历根节点

二叉搜索树：左节点值一定小于根节点，右节点值一定大于根节点

  1. 如果一个序列满足可以拆成 大-小-根，其中的大和小又可以继续拆为大-小-根，直到最小单位，那这个序列就可以反向构建后续遍历搜索二叉树
  2. 因为无法确认左右子树的长度，所以判断依据是当前值是否大于根节点（大于就是仍在右子树，否则就是已经到达左子树了）
  3. 对每一个节点的判断需要：上限值，下限制，如果当前节点在上下限之间，代表一个符合条件的节点
  4. 如果序列中所有节点都符合条件，则返回true，否则返回false

注意：

  1. 一开始设最大最小值是为了避免过大或过小数据无法纳入计算范围
  2. 判断次数会大于实际节点数，应为不知道左右子树数量，所以对于每一个节点（除去最后的根节点）都要判断两次：
    1. （下限，上一节点值）：如果是上一届点的右子树，更新上限，否则保持上限
    2. （上一节点值，上线）：如果是上一届点的左子树，更新下限，否则保持下限、
  3. 实际上两次判断是二律背反，只有其中之一会（可能会）符合条件，不可能两者同时满足，所以如果每个节点都满足，才能说明该序列符合上述1中的条件

Java代码

class Solution {
    int end;
    public boolean verifyPostorder(int[] postorder) {
        if(postorder == null || postorder.length == 1) return true;
        end = postorder.length -1;
        fun(postorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
        return end < 0;
    }

    public void fun(int[] postorder, int min, int max) {
        if(end < 0) return;
        int mid = postorder[end];
        // 判断是否还在当前子树
        if(mid >= max || mid <= min) return;
        end--;
        fun(postorder, mid, max);
        fun(postorder, min, mid);
    }
}