【剑指】4.3 举例具体化抽象问题

这一小节和上一节类似，一些不适合用图而适合直接用数据表示的题目，可以举例子具体化来找出其中的规律。

面试题30：包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O(1)）。

解题思路

使用一个辅助栈来保存当前主栈中的最小值。当要入栈时，比较元素与辅助栈的栈顶，如果辅助栈为空或栈顶元素大于等于要入栈的元素则同时把元素压入辅助栈中；元素从主栈中出栈时，如果辅助栈顶元素相等则也一同出栈。

import java.util.ArrayDeque;
import java.util.Deque;

public class MinStack {
    Deque<Integer> mainStack = new ArrayDeque<>();
    Deque<Integer> minStack = new ArrayDeque<>();

    public void push(int node) {
        if (minStack.isEmpty()||node<=minStack.peek()){
            minStack.push(node);
        }
        mainStack.push(node);
    }

    public void pop() {
        int node = mainStack.pop();
        if (!minStack.isEmpty() && minStack.peek() == node) {
            minStack.pop();
        }
    }

    public int top() {
        return mainStack.isEmpty() ? 0 : mainStack.peek();
    }

    public int min() {
        return minStack.isEmpty() ? Integer.MIN_VALUE : minStack.peek();
    }
}

面试题31：栈的压入、弹出序列

题目描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

解题思路

如果下一个要弹出的数字和栈顶数字相同，那么直接弹出，否则就继续按入栈顺序入栈直到栈顶元素和要弹出的栈顶数字相同为止。如果入栈完毕栈顶和要出栈的元素仍不相等，则不可能是一个弹出序列。

    public boolean isPopOrder(int [] pushA,int [] popA) {
        if (pushA == null || popA == null || pushA.length != popA.length) return false;
        Deque<Integer> stack = new ArrayDeque<>();
        int n = pushA.length, pushIndex = 0;
        outer:
        for (int i = 0; i < n; i++) {
            //如果栈顶元素和当前要弹出的值相同则弹出，开始下一次循环
            if (!stack.isEmpty() && stack.peek() == popA[i]) {
                stack.pop();
                continue;
            }
            //否则直到找到和当前元素相同的值之前，依次将pushA中的元素入栈
            while (pushIndex < n) {
                stack.push(pushA[pushIndex++]);
                //如果发现压入的值和popA当前要弹出的值相同，就在保持i不变的情况下继续下一次外层循环
                if (pushA[pushIndex-1] == popA[i]){
                    i--;
                    continue outer;
                }
            }
            //如果pushA的元素全部入栈都没有和pop[i]相同的
            return false;
        }
        //最后的情况是所有元素都正确入栈、和popA吻合、出栈
        //由第一个continue后i==n，正常结束for循环而没有提前返回false
        return true;
    }

面试题32：从上往下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

解题思路

这一题是二叉树的层次遍历，需要使用队列来辅助完成。

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    ArrayList<Integer> list = new ArrayList<>();
    if (root == null) return list;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        list.add(node.val);
        if (node.left!=null) queue.offer(node.left);
        if (node.right!=null) queue.offer(node.right);
    }
    return list;
}

面试题33：验证序列是否为二叉搜索树的后序遍历序列

题目描述

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

解题思路

序列的最后一个值为BST的根节点，在前面的部分中从左往右比根节点小的属于左子树，一旦发现比根节点大的就认为后面的部分全部属于右子树，如果在后面的部分中发现比根节点小的值说明不是BST。如果两个子树满足性质的话继续对两个子序列执行检查，直到子序列长度小于等于1为止。

public boolean verifySequenceOfBST(int [] sequence) {
    if (sequence == null || sequence.length == 0) {
        return false;
    }
    return verify(sequence, -1, sequence.length);
}

//左右边界为开区间
private boolean verify(int[] sequence, int left, int right) {
    if (right-left <= 1) return true;
    int root = sequence[right-1];
    int mid = left;
    while (true) {
        //如果下一个值开始大于根节点就停止循环
        if (sequence[mid+1]>root) break;
        //如果下一个值就是根节点也停止循环
        if (mid+2==right) break;
        mid++;
    }
    //最终mid是包含左子树元素的最后一个
    for (int i = mid+1; i < right-1; i++) {
        if (sequence[i] < root) return false;
    }
    //如果左子树为空则mid=left，下一层递归中mid+1-left=left+1-left==1，返回true
    //如果右子树为空则mid=right-2，下一层递归中right-1-(right-2)==1，返回true
    return verify(sequence, left, mid+1) && verify(sequence, mid , right - 1);
}

面试题34：二叉树中和为某一值的路径

题目描述

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

解题思路

这一题仍然考查的是二叉树的遍历过程，要找到长度为目标值的路径，可以采用基于DFS的遍历和基于BFS的层次遍历。

层次遍历能保证最短的路径优先被发现，由于使用了队列，想要在节点间传递路径需要额外复制路径并封装到队列中的元素中，写法如下：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class FindTargetPathInTree {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        if (root == null) return result;

        Queue<Pair> queue = new LinkedList<>();
        ArrayList<Integer> initialPath = new ArrayList<>();
        initialPath.add(root.val);
        queue.offer(new Pair(root, initialPath, root.val));
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                Pair pair = queue.poll();
                TreeNode left = pair.node.left, right = pair.node.right;
                if (left == null && right == null && pair.totalLength == target) {
                    result.add(pair.path);
                }else {
                    if (left != null){
                        ArrayList<Integer> nextPath = new ArrayList<>(pair.path);
                        nextPath.add(left.val);
                        queue.offer(new Pair(left, nextPath, pair.totalLength + left.val));
                    }
                    if (right != null) {
                        ArrayList<Integer> nextPath = new ArrayList<>(pair.path);
                        nextPath.add(right.val);
                        queue.offer(new Pair(right, nextPath, pair.totalLength + right.val));
                    }
                }
            }
        }
        return result;
    }

    private class Pair{
        TreeNode node;
        ArrayList<Integer> path;
        int totalLength;

        public Pair(TreeNode node, ArrayList<Integer> path, int totalLength) {
            this.node = node;
            this.path = path;
            this.totalLength = totalLength;
        }
    }
}

牛客网上相较于原书多了一个字典序的要求，而显然不可能出现符合条件的两条路径使得一条包含了另一条，所以这里字典序就不需要考虑长短问题，只需要考虑在一个节点使用回溯方法作选择时是先选左孩子还是先选右孩子。

class FindTargetPathInTree2{
    ArrayList<ArrayList<Integer>> result=new ArrayList<>();
    int target = 0;

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if (root == null) return result;
        this.target = target;
        dfs(root,new ArrayList<>(),0);
        return result;
    }

    private void dfs(TreeNode node, ArrayList<Integer> path, int pathLength) {
        ArrayList<Integer> currentPath = new ArrayList<>(path);
        currentPath.add(node.val);
        if (node.left == null && node.right == null ) {
            if (pathLength + node.val == target) {
                result.add(currentPath);
            }
            return;
        }
        if (node.left == null) {
            dfs(node.right, currentPath, pathLength + node.val);
            return;
        }
        if (node.right == null) {
            dfs(node.left, currentPath, pathLength + node.val);
            return;
        }
        if (node.left.val < node.right.val) {
            dfs(node.left, currentPath, pathLength + node.val);
            dfs(node.right, currentPath, pathLength + node.val);
        } else {
            dfs(node.right, currentPath, pathLength + node.val);
            dfs(node.left, currentPath, pathLength + node.val);
        }
    }
}