剑指offer计划20（搜索与回溯算法中等）---java

Love The Way You Lie 2022-09-12 04:53 182阅读 0赞

## 1.1、题目1 ##

剑指 Offer 07. 重建二叉树

## 1.2、解法 ##

注释解法。

## 1.3、代码 ##

class Solution {
        int[] preorder;
        HashMap<Integer, Integer> map = new HashMap<>();
        // 前序遍历 preorder: 根 -- 左 -- 右   第一个肯定是根节点
        // 中序遍历 inorder: 左 -- 根 -- 右
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            this.preorder = preorder;
            for(int i = 0; i < inorder.length; i++){
                map.put(inorder[i], i);
            }
            return rebuild(0, 0, inorder.length - 1);  
        }
    
        // pre_root_index : 根节点 在 前序遍历中的下标
        // in_left_index: 该节点在中序遍历中的左边界
        // in_right_index: 该节点在中序遍历中的右边界
        public TreeNode rebuild(int pre_root_index, int in_left_index, int in_right_index){
           if(in_left_index > in_right_index)  return null;
           // 根节点在中序遍历中的位置：in_root_index
           int in_root_index = map.get(preorder[pre_root_index]);
           // 创建一个根节点
           TreeNode node = new TreeNode(preorder[pre_root_index]);
           // 寻找node的左节点: 
           // 在前序遍历中的位置就是  根节点的下标 + 1（右边一个单位）
           // 在中序遍历中的位置就是： 1. 左边界不变，2. 右边界就是根节点的左边一个单位 in_root_index - 1
           node.left = rebuild(pre_root_index + 1, in_left_index, in_root_index - 1);
           // 寻找node的右节点: 
           // 在前序遍历中的位置就是  根节点的下标 + 左子树长度 + 1
           // 在中序遍历中的位置就是： 1. 左边界在根节点的右边一个单位  in_root_index + 1, 2. 右边界不变
           node.right = rebuild(pre_root_index + in_root_index - in_left_index + 1, in_root_index + 1, in_right_index);
           return node;
        }
    }

## 2.1、题目2 ##

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

## 2.2、解法 ##

分类讨论，判断内容，通过将数拆开两半来减少性能消耗（容易栈溢出）

## 2.3、代码 ##

class Solution {
        public double myPow(double x, int n) {
            if(n<0) return 1/(x*myPow(x,-n-1)) ;
            else if(n==0) return 1;
            else if(n==1) return x;
            else{
                double res=myPow(x,n/2);
                return res*res*myPow(x,n%2);
            
            }
        }
    }

## 3.1、题目3 ##

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

## 3.2、解法 ##

递归开始判断，找到第一个大于根节[java教程][java]点的值，然后找出左子树和右子树的两个区间，  
通过递归再次判断

## 3.3、代码 ##

class Solution {
        public boolean verifyPostorder(int[] postorder) {
            return recur(postorder,0,postorder.length - 1);
        }
        boolean recur(int[] postorder, int start, int end){
            if(start >= end) return true;
            int temp = start; 
            // 找到右子树结点第一次出现的地方。（或者说是遍历完整棵左子树）
            for(int i = start; i <= end; ++i){
                if(postorder[i] < postorder[end]){
                    temp = i;
                }
                else break;
            }
            int rightTreeNode = temp + 1; // 后序遍历右子树时会访问的第一个结点的下标。
            // 验证右子树所有结点是否都大于根结点。
            for(int i = rightTreeNode; i <= end; ++i){
                if(postorder[i] > postorder[end])
                    ++rightTreeNode;
            }
            return rightTreeNode == end && recur(postorder,start,temp) && recur(postorder,temp + 1,end - 1);
        }
    }

[java]: https://www.xin3721.com/eschool/Javaxin3721/