[java刷算法]牛客—剑指offer2链表与树的练习理解

• 率‍♂️个人主页：杯咖啡
• 进步是今天的活动，明天的保证！
• ✨目前正在学习：SSM框架,算法刷题
• 牛客网，刷算法过面试的神级网站，用牛客你也牛。 免费注册和我一起学习刷题
• 希望大家多多支持殺一起进步呀！
• Love is the one thing we’re capable of perceing that transcends time and space.
  爱是我们唯一能够感知的可以超越时空维度的事物。

JZ6 从尾到头打印链表
JZ7 重建二叉树
JZ8 二叉树的下一个结点

• ✨今日三剑
• JZ6 从尾到头打印链表
• • 题目描述
  • 思路详解
  • 代码与结果
• JZ7 重建二叉树
• • 题目描述
  • 思路详解
  • 代码与结果
• JZ8 二叉树的下一个结点
• • 题目描述
  • 思路详解
  • 代码与结果
• ✨总结

本题的我们都知道单链表没办法从末尾到头来遍历，更别说输出了。
但是我们可以想到递归的本质栈，先进后出，我们可以用递归的办法，先递归到最深处在开始添加到数组。这样利用栈的本质，他不就自动逆序了吗。

我们在做题的时候，一看到逆序就要首先想到栈的本质哦，下面看代码。

import java.util.ArrayList;
public class Solution {
    //递归函数
    public void recursion(ListNode head, ArrayList res){
        if(head != null){
            //先往链表深处遍历
            recursion(head.next, res);
            //再填充到数组就是逆序
            res.add(head.val);
        }
    }
    public ArrayList printListFromTailToHead(ListNode listNode) {
        ArrayList res = new ArrayList();
        //递归函数解决
        recursion(listNode, res);
        return res;
    }
}

根据前序，中序构建出树，也是面试官更倾向于考的，也有一定的难度。
这里采用递归的方法，我们知道，前序是根写在最前，中序根写在中间，那么中序就有着分树的作用。前序就有着找根的作用。
我们每次在前序拿到根，就去中序里面找，找到之后就会发现树被分成了左子树和右子树的小树，那么我们就对其分而治之。
这里有个需要注意的点，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;
    }
}

本题主要考察树的中序遍历和构造。
那么我们首先获取到所有的根节点，然后通过中序遍历构造出树，最后进行匹配就可以了。
这里需要注意的是对树的理解以及构造的过程，小伙伴们可以在大脑中模拟一下哦。

import java.util.*;


public class Solution {
    ArrayList 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);
        }
    }
}

到这里今日的三剑就结束了，链表和树，在面试的时候也是面试官和喜欢问的问题，它不仅考察了你的编程能力，更考察你的逻辑思维。小伙伴有时间可以多理解一下，多多练习哦。明天见，拜了个白~~

原 创 不 易 ， 还 希 望 各 位 大 佬 支 持 一 下 textcolor{blue}{原创不易，还希望各位大佬支持一下} 原创不易，还希望各位大佬支持一下

点 赞 ， 你 的 认 可 是 我 创 作 的 动 力 ！ textcolor{green}{点赞，你的认可是我创作的动力！} 点赞，你的认可是我创作的动力！

收 藏 ， 你 的 青 睐 是 我 努 力 的 方 向 ！ textcolor{green}{收藏，你的青睐是我努力的方向！} 收藏，你的青睐是我努力的方向！

评 论 ， 你 的 意 见 是 我 进 步 的 财 富 ！ textcolor{green}{评论，你的意见是我进步的财富！} 评论，你的意见是我进步的财富！