原创

剑指offer(二) 重建二叉树+用两个栈实现队列+旋转数组的最小数字

记录并复习一下剑指offer的部分题型~ @[TOC]


重建二叉树

题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。


首先给我们的条件是一个前序遍历的数组和中序遍历的数组。需要注意的是中序遍历的数组,要知道前序遍历的第一个值,就是中序遍历的中间值。所以我们可以通过前序遍历的顺序将中序遍历分割成一个个的小范围,然后通过递归进行查找。

举个栗子:前序遍历:{1,2,4,7,3,5,6,8},中的第一个值1,在中序遍历(4,7,2,1,5,3,8,6)的位置,是正好的中间值,那么可以将中序遍历分为{4,7,2}和{5,3,8,6}两个数组。{4,7,2}数组即为1节点的左边,{5,3,8,6}数组即为1节点的右边,之后只需要进行遍历前序遍历数组,将遍历到的第一个值放入中序遍历的范围中查找。这里并不是说要真的切割数组,只要记录下切割数组的下标即可。 当然由很多更好的办法可以更快..具体看代码吧~

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        //int [] pre 前序数组
        //int [] in  中序数组
        //获得前序比那里第一个元素
        TreeNode treeNode = new TreeNode(pre[0]);
        //设置下标为 0
        int index = 0;
        //遍历中序数组
        for (int i = 0; i < in.length; i++) {
            //找到对应的数字后退出 index记录下标
            if (pre[0] == in[i]){
                index = i;
                break;
            }
        }
        //调用方法,表示第一个元素的左子树在这个方法中返回 
        treeNode.left = ConstructProcess(pre, in, 0, index);
        treeNode.right = ConstructProcess(pre, in, index + 1, pre.length);
        //返回头结点
        return treeNode;
    }
        public static TreeNode ConstructProcess(int[] pre, int[]in, int begin, int end){
        //当输入的开始下标小于结束下标时继续
        if (begin < end){
            int index = 0;
            //设置外围循环的名字为outer
            outer:
            //遍历前序遍历数组
            for(int i:pre){
                //设置一个j下标作为是否在限定范围里的判断
                for (int j = 0; j < pre.length; j++) {
                    //如果j在范围里并且i的值正好能在中序数组中找到
                    if (j>= begin && j <end && i == in[j]){、
                        //设置下标为j
                        index = j;
                        //退出外循环
                        break outer;
                    }
                }
            }
            //设置当前节点为中序遍历找到的节点
            TreeNode treeNode= new TreeNode(in[index]);
            //递归获取左子树和右子树
            treeNode.left = ConstructProcess(pre, in, begin, index);
            treeNode.right = ConstructProcess(pre, in, index + 1, end);
            //返回当前节点
            return treeNode;
        }
        //不然返回null
        return null;
    }
}

用两个栈实现队列

题目描述 用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。


通过两个栈实现一个队列的添加和pop弹出操作。那么我们可以创建两个栈,1号栈作为push元素的栈,二号栈作为pop元素的栈,当二号栈为空时,再将1号栈里的元素pop到二号栈中。

知识补充:如何用两个栈实现队列? 只需要将需要传入的元素先add到第一个栈中,然后由第一个栈pop,然后add到第二个栈中,这样第二个栈pop出去的元素就是队列的形式。就以这个基础做这个题。

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        //第一个栈中添加元素
        stack1.add(node);
    }
    
    public int pop() {
       //当第二个栈为空时
       if (stack2.size() == 0){
           while (stack1.size() != 0){
               //只要第一个栈不为空,就将剩余元素都放到二号栈中
               stack2.push(stack1.pop());
           }
       }
        //进行二号栈的pop()
        return stack2.pop();
    }
}

旋转数组的最小数字

题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。


..看题目好像很复杂的,做的时候还想了好一会。本意应该是给一个有序数组,然后把后面n个数字调换到了前面,然后输出最小值。想了想记录第一个值max,然后遍历找到第一个比max小的值就是答案。

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        //当数组为0,则返回
        if(array.length == 0) return 0;
        //设置第一个值为max
        int max = array[0];
        //从第二个值开始遍历
        for(int i=1;i<array.length;i++){
            //当max大于这个值时,说明这个值就是最小值,因为这是有序数组
            if(max > array[i]){
                return array[i];
            }
        }
        return max;
    }
}
java
算法
二叉树

  • 作者:LinJy(联系作者)
  • 发表时间:2020-05-09 15:22
  • 版权声明:自由转载-非商用-非衍生-保持署名(null)
  • undefined
  • 评论

    留言