剑指Offer之Java算法习题精讲二叉树专题篇上

一、前言

二叉树是算法中非常重要的数据结构，也是面试时常被考察的知识点。在这篇文章中，我们会详细讲解剑指Offer中关于二叉树的Java算法习题精讲，帮助读者更好地掌握二叉树的相关知识。

二、题目汇总

下面是本篇文章中涉及的二叉树习题题目汇总：

题目编号	题目名称	题目描述
4	重构二叉树	输入前序遍历和中序遍历结果，重构二叉树
5	用两个栈实现队列	用两个栈来实现一个队列，完成队列的Push和Pop操作
6	旋转数组的最小数字	把一个数组最开始的若干个元素搬到数组的末尾,找出最小元素
7	斐波那契数列	求斐波那契数列的第n项
8	跳台阶	一个台阶由n个阶梯组成，一次可以跳1级或者2级，求跳这个台阶有多少种方法
9	变态跳台阶	一个台阶由n个阶梯组成，一次可以跳1级，也可以跳2级……它也可以跳上去n级。 求该台阶有多少种跳法
10	矩形覆盖	我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形，请问用n个2 * 1的小矩形无重叠地覆盖一个2 * n的大矩形，总共有多少种方法
11	二进制中1的个数	输入一个整数，输出该数二进制表示中1的个数。
12	数值的整数次方	实现函数double Power(double base, int exponent)，求base的exponent次方。
13	调整数组顺序使奇数位于偶数前面	输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分
14	链表中倒数第k个结点	输入一个链表，输出该链表中倒数第k个结点
15	反转链表	输入一个链表，反转链表后，输出新链表的表头
16	合并两个排序的链表	输入两个单调递增的链表，输出两个链表合成后的链表
17	树的子结构	输入两棵二叉树A和B，判断B是不是A的子结构
18	二叉树的镜像	操作给定的二叉树，将其变换为源二叉树的镜像
19	顺时针打印矩阵	输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字
20	包含min函数的栈	定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））
21	栈的压入、弹出序列	输入两个整数序列，第一个序列表示栈的压入顺序，判断第二个序列是否为该栈的弹出顺序
22	从上往下打印二叉树	从上往下打印出二叉树的每个节点，同层节点从左至右打印
23	二叉搜索树的后序遍历序列	输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
24	二叉树中和为某一值的路径	输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

三、题目讲解

下面将对题目中的几个重要题目进行讲解。

3.1 重构二叉树

本题要求把输入的前序遍历和中序遍历结果，重构出二叉树并返回重构后的二叉树的根节点。这里给出两种解法，一种是递归实现，另一种是迭代实现。

3.1.1 解法一：递归实现

public class Solution {
    int preIndex = 0; //前序遍历的索引
    Map<Integer,Integer> inorderMap = new HashMap<>();//中序遍历的位置哈希表

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length != inorder.length){
            return null;
        }
        //初始化中序遍历的位置哈希表
        for(int i = 0;i < inorder.length;i++){
            inorderMap.put(inorder[i],i);
        }
        // 构建二叉树
        return buildTree(preorder, inorder, 0, preorder.length -1);
    }

    private TreeNode buildTree(int[] preorder, int[] inorder, int start, int end) {
        if(start > end){
            return null;
        }
        //选择前序遍历的首节点作为根节点
        int rootVal = preorder[preIndex++];
        TreeNode root = new TreeNode(rootVal);
        //根据根节点将中序遍历结果分为左右两部分
        int rootIndex = inorderMap.get(rootVal);
        root.left = buildTree(preorder, inorder, start, rootIndex -1);
        root.right = buildTree(preorder, inorder, rootIndex + 1, end);
        return root;
    }
}

递归实现的思路是先根据前序遍历第一个节点创建出根节点，然后在中序遍历中找到该根节点的位置。由于中序遍历的特点是根节点左侧为左子树，右侧为右子树，因此可以得到左右子树的范围，继续递归即可。时间复杂度为O(n)。

3.1.2 解法二：迭代实现

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || inorder == null || preorder.length != inorder.length){
            return null;
        }
        Stack<TreeNode> stack = new Stack<>();
        int preIndex = 0;
        TreeNode root = new TreeNode(preorder[preIndex++]);
        stack.push(root);
        //迭代构建二叉树
        for(int i = 0;i < inorder.length;i++){
            TreeNode node = stack.peek();
            if(node.val != inorder[i]){
                node.left = new TreeNode(preorder[preIndex++]);
                stack.push(node.left);
            }else{
                while(!stack.isEmpty() && stack.peek().val == inorder[i]){
                    node = stack.pop();
                }
                node.right = new TreeNode(preorder[preIndex++]);
                stack.push(node.right);
            }
        }
        return root;
    }
}

迭代实现的思路是用一个栈来模拟递归过程，先根据前序遍历的结果创建根节点，并将其入栈。从中序遍历的第一个节点开始遍历，如果当前节点与栈顶节点值相同，则可以将栈顶节点弹出，将当前节点作为其右子节点并入栈；否则，将当前节点作为栈顶节点的左子节点并入栈。时间复杂度也为O(n)。

3.2 用两个栈实现队列

本题要求用两个栈来实现一个队列，完成队列的Push和Pop操作。

public class Solution {
    private Stack<Integer> stack1 = new Stack<>();
    private Stack<Integer> stack2 = new Stack<>();

    public void push(int node) {
        stack1.push(node);
    }

    public int pop() {
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

本题需要注意的是，由于栈是先进后出的结构，而队列是先进先出的结构，因此需要借助两个栈进行转换。具体实现即：栈1用于入队操作，栈2用于出队操作。当栈2为空时，将栈1中的元素逐个出栈，并依次压入栈2。出队操作就是从栈2中弹出栈顶元素。由于每个元素至多进栈出栈两次，因此时间复杂度为O(1)。

四、总结

本篇文章讲解了剑指Offer中涉及的二叉树习题，并针对部分常考题目进行了详细解释。掌握了这些题目的解法，读者对于二叉树的相关知识将更加深入和熟练。