Java后端开发算法基础面试题分享，你离大厂也许就差这份面试题

朴灿烈づ我的快乐病毒、 2023-09-28 08:40 166阅读 0赞

## 一、算法基础 ##

**1. 重建二叉树**

**题目**：

输入一棵二叉树前序遍历和中序遍历的结果，请重建该二叉树。

**注意**：

*  二叉树中每个节点的值都互不相同；
 *  输入的前序遍历和中序遍历一定合法；

**演示**：

> 给定：  
> 前序遍历是：\[3, 9, 20, 15, 7\]  
> 中序遍历是：\[9, 3, 15, 20, 7\]

> 返回：\[3, 9, 20, null, null, 15, 7, null, null, null, null\]  
> 返回的二叉树如下所示：![fd761d26aa7b43c9ad273010286bb0f5.png][]

**分析**：

前序的第一个字母肯定是父节点, 然后再去中序找该节点对应的位置, 位置前是左子树, 后是右子树。以此类推。

**代码**：

class Solution {
        Map<Integer,Integer> map = new HashMap<>();
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            
            for(int i = 0 ; i< inorder.length; i++){
                map.put(inorder[i],i);
            }
            return dfs(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
        }
        
        public TreeNode dfs(int [] preorder, int [] inorder, int pl, int pr, int il, int ir){
            if(pl > pr){
                return null;
            }
            TreeNode root = new TreeNode(preorder[pl]);
            int k = map.get(preorder[pl])-il;
            root.left = dfs(preorder,inorder,pl+1,pl+k,il,il+k-1);
            root.right = dfs(preorder,inorder,pl+k+1,pr,il+k+1,ir);
            return root;
        }
    }

**2. 替换空格**

**题目**：

请实现一个函数，把字符串中的每个空格替换成"%20"。

你可以假定输入字符串的长度最大是1000。 注意输出字符串的长度可能大于1000。

**演示**：

> 输入："We are happy."  
> 输出："We%20are%20happy."

**分析**：

考察对char的处理

**代码**：

class Solution {
        public String replaceSpaces(StringBuffer str) {
            char[] chars = str.toString().toCharArray();
            StringBuffer result = "";
            for(char i:chars){
                if(i == ' '){
                    result.append("%20");
                }else{
                    result.append(i);
                }
            }
            return result.toString();
        }
    }

**3. 二叉搜索树的后序遍历序列**

**题目**：

输入一个整数数组，判断该数组是不是某二叉搜索

[fd761d26aa7b43c9ad273010286bb0f5.png]: https://img-blog.csdnimg.cn/fd761d26aa7b43c9ad273010286bb0f5.png