✨今日三剑
文章目录
JZ6 从尾到头打印链表
题目描述
思路详解
本题的我们都知道单链表没办法从末尾到头来遍历，更别说输出了。
但是我们可以想到递归的本质栈，先进后出，我们可以用递归的办法，先递归到最深处在开始添加到数组。这样利用栈的本质，他不就自动逆序了吗。
我们在做题的时候，一看到逆序就要首先想到栈的本质哦，下面看代码。
代码与结果
import java.util.ArrayList; public class Solution { //递归函数 public void recursion(ListNode head, ArrayList<Integer> res){ if(head != null){ //先往链表深处遍历 recursion(head.next, res); //再填充到数组就是逆序 res.add(head.val); } } public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { ArrayList<Integer> res = new ArrayList<Integer>(); //递归函数解决 recursion(listNode, res); return res; } }
JZ7 重建二叉树
题目描述
思路详解
根据前序，中序构建出树，也是面试官更倾向于考的，也有一定的难度。
这里采用递归的方法，我们知道，前序是根写在最前，中序根写在中间，那么中序就有着分树的作用。前序就有着找根的作用。
我们每次在前序拿到根，就去中序里面找，找到之后就会发现树被分成了左子树和右子树的小树，那么我们就对其分而治之。
这里有个需要注意的点，Arrays.copyOfRange(pre, 1, i + 1) 数组复制方法包括前下标，不包括后下标[1，i + 1）
那么小伙伴可以思考一下给你后序和中序的构造方法哦，欢迎评论区讨论。
代码与结果
import java.util.*; public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] vin) { int n = pre.length; int m = vin.length; //每个遍历都不能为0 if(n == 0 || m == 0) return null; //构建根节点 TreeNode root = new TreeNode(pre[0]); for(int i = 0; i < vin.length; i++){ //找到中序遍历中的前序第一个元素 if(pre[0] == vin[i]){ //构建左子树 root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(vin, 0, i)); //构建右子树 root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(vin, i + 1, vin.length)); break; } } return root; } }
JZ8 二叉树的下一个结点
题目描述
思路详解
本题主要考察树的中序遍历和构造。
那么我们首先获取到所有的根节点，然后通过中序遍历构造出树，最后进行匹配就可以了。
这里需要注意的是对树的理解以及构造的过程，小伙伴们可以在大脑中模拟一下哦。
代码与结果
import java.util.*; /* public class TreeLinkNode { int val; TreeLinkNode left = null; TreeLinkNode right = null; TreeLinkNode next = null; TreeLinkNode(int val) { this.val = val; } } */ public class Solution { ArrayList<TreeLinkNode> nodes = new ArrayList<>(); public TreeLinkNode GetNext(TreeLinkNode pNode) { // 获取根节点 TreeLinkNode root = pNode; while(root.next != null) root = root.next; // 中序遍历打造nodes InOrder(root); // 进行匹配 int n = nodes.size(); for(int i = 0; i < n - 1; i++) { TreeLinkNode cur = nodes.get(i); if(pNode == cur) { return nodes.get(i+1); } } return null; } // 中序遍历 void InOrder(TreeLinkNode root) { if(root != null) { InOrder(root.left); nodes.add(root); InOrder(root.right); } } }
✨总结
到这里今日的三剑就结束了，链表和树，在面试的时候也是面试官和喜欢问的问题，它不仅考察了你的编程能力，更考察你的逻辑思维。小伙伴有时间可以多理解一下，多多练习哦。明天见，拜了个白~~
