面试题【30-34】举例让抽象问题具体化

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

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O(1)。

• 算法：
  • 两个栈：
  • 主栈照常出栈入栈
  • 最小栈每次入栈小于等于栈顶的元素，出栈照常

class MinStack {
    Stack<Integer> main;
    Stack<Integer> min;
    public MinStack() {
        main = new Stack<Integer>();
        min = new Stack<Integer>();
    }
    public void push(int x) {
        main.push(x);
        if (min.isEmpty() || x < min.peek()) {
            min.push(x);
        } else {
            min.push(min.peek());
        }
    }
    public void pop() {
        if (!main.empty()) {
            main.pop();
        }
        if (!min.empty()) {
            min.pop();
        }
    }
    public int top() {
        if (!main.empty()) {
            return main.peek();
        } else {
            return -1;
        }
    }
    public int getMin() {
        if (!min.empty()) {
            return min.peek();
        } else {
            return -1;
        }
    }
}

• 算法：
  • 只用一个栈
  • 入栈元素小于当前min就入栈两次同时更新min（当前min和x）
  • 出栈元素等于当前min就出栈两次同时更新min

class MinStack {
    int min;
    Stack<Integer> stack;
    public MinStack() {
        min = Integer.MAX_VALUE;
        stack = new Stack<Integer>();
    }
    public void push(int x) {
        // first push the last minimum value 
        // when the current minimum value changes after pushing the new value x
        if(x <= min){
            stack.push(min);
            min=x;
        }
        stack.push(x);
    }
    public void pop() {
        // if pop operation could result in the changing of the current minimum value,
        // pop twice and change the current minimum value to the last minimum value.
        if(stack.pop() == min) 
            min = stack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return min;
    }
}

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

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

• 算法：push序列不断压栈直到遇到pop序列的出栈元素

// 遍历出栈序列
public boolean validateStackSequences(int[] pushed, int[] popped) {
    if (pushed == null || popped == null) {
        throw new RuntimeException("Null");
    }
    if (pushed.length != popped.length) {
        return false;
    }
    if (pushed.length == 0 && popped.length == 0) {
        return true;
    }

    int pushIndex = 0;
    int popIndex = 0;
    Stack<Integer> stack = new Stack<Integer>();
    while (popIndex < popped.length) {
        while ((stack.empty() || stack.peek() != popped[popIndex]) && pushIndex < pushed.length) {
            stack.push(pushed[pushIndex++]);
        }

        if (stack.peek() == popped[popIndex]) {
            stack.pop();
            popIndex++;
        } else {
            return false;
        }
    }
    return true;
}

// 遍历出栈序列
public boolean validateStackSequences(int[] pushed, int[] popped) {
    if (pushed == null || popped == null) {
        throw new RuntimeException("Null");
    }
    if (pushed.length != popped.length) {
        return false;
    }
    if (pushed.length == 0 && popped.length == 0) {
        return true;
    }

    Stack<Integer> stack = new Stack<Integer>();
    int index = 0;
    for (int p : pushed) {
        stack.push(p);
        while (!stack.isEmpty() && stack.peek() == popped[index]){
            stack.pop();
            index++;
        }
    }
    return stack.isEmpty();
}

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

题目一：不分行从上到下打印二叉树

题目：从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。

public int[] levelOrder(TreeNode root) {
    if (root == null) {
        return new int[0];
    }

    List<Integer> result = new ArrayList<Integer>();
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode temp = queue.poll();
        result.add(temp.val);
        if (temp.left != null) {
            queue.offer(temp.left);
        }
        if (temp.right != null) {
            queue.offer(temp.right);
        }
    }

    int[] array = new int[result.size()];
    int i = 0;
    for (Integer x : result) {
        array[i++] = x;
    }
    return array;
}

题目二：分行从上到下打印二叉树

题目：从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。

• 算法：分层收集打印

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if(root == null)
        return res;

    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelNum = queue.size();
        List<Integer> levelList = new ArrayList<Integer>();
        for (int i = 0; i < levelNum; i++) {
            TreeNode temp = queue.peek();
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
            levelList.add(queue.poll().val);
        }
        res.add(levelList);
    }
    return res;
}

• 算法：分层计数打印

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if (root == null) {
        return res;
    }

    int nextLevel = 0;
    int currLevel = 1;
    ArrayList<Integer> level = new ArrayList<Integer>();
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode temp = queue.poll();
        level.add(temp.val);
        currLevel--;
        if (temp.left != null) {
            queue.offer(temp.left);
            nextLevel++;
        }
        if (temp.right != null) {
            queue.offer(temp.right);
            nextLevel++;
        }
        if (currLevel == 0) {
            res.add(level);
            level = new ArrayList<Integer>();
            currLevel = nextLevel;
            nextLevel = 0;
        }
    }
    return res;
}

题目三：之字形打印二叉树

题目：请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

• 算法：
  • 两个栈：从1开始计算层数
  • 栈1收集奇数层先右节点后左子节点，栈2收集偶数层先左子节点后右子节点

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if (root == null) {
        return res;
    }

    int curr = 0;
    int next = 1;
    ArrayList<Integer> levelList = new ArrayList<Integer>();
    Stack<TreeNode> stack1 = new Stack<TreeNode>();
    Stack<TreeNode> stack2 = new Stack<TreeNode>();
    stack1.push(root);
    while (!stack1.empty() || !stack2.empty()) {
        if (curr == 0) {
            TreeNode temp = stack1.pop();
            levelList.add(temp.val);
            if (temp.left != null) {
                stack2.push(temp.left);
            }
            if (temp.right != null) {
                stack2.push(temp.right);
            }
            if (stack1.empty()) {
                res.add(levelList);
                levelList = new ArrayList<>();
                curr = 1 - curr;
                next = 1 - next;
            }
        } else {
            TreeNode temp = stack2.pop();
            levelList.add(temp.val);
            if (temp.right != null) {
                stack1.push(temp.right);
            }
            if (temp.left != null) {
                stack1.push(temp.left);
            }
            if (stack2.empty()) {
                res.add(levelList);
                levelList = new ArrayList<>();
                curr = 1 - curr;
                next = 1 - next;
            }
        }
    }
    return res;
}

• 算法：
  • 双端队列：
  • 奇数层和偶数层按规律添加和删除

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null) {
            return res;
        }

        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while(!deque.isEmpty()) {
            // 奇数层：队尾删除，队首先左后右添加，使得下一个偶数层从右向左打印
            List<Integer> levelList = new ArrayList<>();
            for(int i = deque.size(); i > 0; i--) {
                TreeNode node = deque.removeLast();
                levelList.add(node.val);
                if(node.left != null) deque.addFirst(node.left);
                if(node.right != null) deque.addFirst(node.right);
            }
            res.add(levelList);
            if (deque.isEmpty()) break;
            // 偶数层：队首删除，队尾先右后左添加，使得下一个奇数层从左向右打印
            levelList = new ArrayList<>();
            for(int i = deque.size(); i > 0; i--) {
                TreeNode node = deque.removeFirst();
                levelList.add(node.val);
                if(node.right != null) deque.addLast(node.right);
                if(node.left != null) deque.addLast(node.left);
            }
            res.add(levelList);
        }
        return res;
}

面试题33：二叉搜索树的后序遍历序列

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

• 算法：
  • 利用最后一个数组元素是树的根节点来分割这个二叉搜索树，递归处理左右子树

public boolean verifyPostorder(int[] postorder) {
    if (postorder == null) {
        throw new RuntimeException("Array is null");
    }
    if (postorder.length <= 1) {
        return true;
    }

    return verifyPostorderRecursion(postorder, 0, postorder.length - 1);
}
private boolean verifyPostorderRecursion(int[] postorder, int start, int end) {
    if (start == end) {
        return true;
    }

    int root = postorder[end];
    int i = start;
    for (; i < end; i++) {
        if (postorder[i] > root)  {
            break;
        }
    }
    int j = i;
    for (; j < end; j++) {
        if (postorder[j] < root) {
            return false;
        }
    }
    boolean left = true;
    boolean right = true;
    if (i > start) {
        left = verifyPostorderRecursion(postorder, start, i - 1);
    }
    if (i < end) {
        right = verifyPostorderRecursion(postorder, i, end - 1);
    }
    return left && right;
}

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

题目：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

public List<List<Integer>> pathSum(TreeNode root, int sum) {
    List<List<Integer>> result = new LinkedList<List<Integer>>();
    if (root == null) {
        return result;
    }

    LinkedList<Integer> path = new LinkedList<Integer>();
    findPath(root, result, path, sum, 0);
    return result;
}

private void findPath(TreeNode node, List<List<Integer>> result, LinkedList<Integer> path,
                        int pathSum, int currentSum) {
    currentSum += node.val;
    path.offer(node.val);
    if (node.left == null && node.right == null && currentSum == pathSum) {
        LinkedList<Integer> temp = new LinkedList<Integer>();
        temp.addAll(path);
        result.add(temp);
    }
    if (node.left != null) {
        findPath(node.left, result, path, pathSum, currentSum);
    }
    if (node.right != null) {
        findPath(node.right, result, path, pathSum, currentSum);
    }
    path.pollLast();
}