本文按照牛客网的顺序，牛客网剑指offer刷题网址：https://www.nowcoder.com/ta/coding-interviews

本文涉及的题目：
1、二维数组中的查找
2、从尾到头打印链表
3、重建二叉树

1、二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路
类似于二分查找，根据题目，如果拿数组中任意一个元素与目标数值进行比较，如果该元素小于目标数值，那么目标数值一定是在该元素的下方或右方，如果大于目标数值，那么目标数值一定在该元素的上方或者左方。

对于二分查找来说，每次比较只能移动一个指针，同时，指针的移动方向必须在查找过程中保持一致。在二维数组的查找中，两个指针是一个上下方向移动，一个是左右方向移动的。两个指针可以从同一个角出发，也可以从不同的角出发。这里我们只考虑从同一个角出发的情况。

假设我们从左上角出发，也就是row=0 和 col=0，如果元素小于目标数值，我们会将row往下移或着col往右移，这样，被屏蔽的区域可能会是目标元素所在的区域。比如row+=1，那么第一行除左上角以外的元素就被忽略了，如果col+=1，那么第一列出左上角以外的元素就被忽略了。因此这样是不可行的。

所以本题从右上角出发寻找解题思路，即开始时col=len(array[0])-1,row=0,col往左移动，row往下移动，当某元素小于目标数值时，col-=1，而当某元素大于目标数值时，row+=1。代码如下：

java

public class Solution {
    public boolean Find(int target, int [][] array) {
        int row = 0;
        int col = array[0].length-1;
        while(row<array.length && col>=0){
            if(array[row][col] == target)
                return true;
            else if(array[row][col] > target)
                col -= 1;
            else
                row += 1;
        } 
        return false;
    }
}

python

# -*- coding:utf-8 -*-
class Solution:
    def Find(self, target, array):
        # write code here
        if not array:
            return False
        row = 0
        col = len(array[0])-1
        while row < len(array) and col >=0:
            if array[row][col] == target:
                return True
            elif array[row][col] < target:
                row = row + 1
            else:
                col = col - 1
        return False
           

2、从尾到头打印链表

问题描述
输入一个链表，从尾到头打印链表每个节点的值。

思路解析
使用栈从头到尾push链表的元素，然后pop所有的元素到一个list中并返回

代码实现
java

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        ListNode p = listNode;
        ArrayList<Integer> stack = new ArrayList<Integer>();
        while(p!=null){
            stack.add(p.val);
            p = p.next;
        }
        int n = stack.size();
        for(int i=n-1;i>=0;i--){
            arr.add(stack.get(i));
        }
        return arr;
        
    }
}

python

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def printListFromTailToHead(self, listNode):
        # write code here
        if not listNode:
            return []
        p = listNode
        stack = []
        res = []
        while p:
            stack.append(p.val)
            p = p.next
        for i in range(len(stack)-1,-1,-1):
            res.append(stack[i])
        return res

3、重建二叉树

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

思路解析
根据前序遍历的结果，对于输入的遍历序列，第一个数一定是根结点，那么我们去中序遍历的结果中找到该根节点，中序遍历结果中根结点左边的是左子树的节点，右边的是右子树的节点，这样很容易使用递归的思路实现二叉树的重建。

代码实现
java

/**
 * 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) {
        if(pre == null || in == null || pre.length == 0 || in.length == 0){
            return null;
        }
        return buildTree(pre, in, 0, pre.length - 1, 0, in.length - 1);
    }
    public TreeNode buildTree(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd){
        TreeNode root = new TreeNode(pre[preStart]);
        int rootIn = 0;
        for(; rootIn < in.length; rootIn++){
            if(in[rootIn] == root.val){
                break;
            }
        }
        int leftLength = rootIn - inStart;
        int rightLength = inEnd - rootIn;
        if(leftLength > 0){
            root.left = buildTree(pre, in, preStart + 1, preStart + leftLength, inStart, rootIn - 1);           
        }
        if(rightLength > 0){
            root.right = buildTree(pre, in, preStart + leftLength + 1, preEnd, rootIn + 1, inEnd);   
        }
         
        return root;
    }
}

python

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def reConstructBinaryTree(self, pre, tin):
        # write code here
        if not pre or not tin:
            return None
        root = TreeNode(pre[0])
        i = 0
        while i < len(tin):
            if tin[i] == pre[0]:
                break
            i = i + 1
        index = i
        root.left = self.reConstructBinaryTree(pre[1:index+1],tin[:index])
        root.right = self.reConstructBinaryTree(pre[index+1:],tin[index+1:])
        return root