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

🧛‍♂️个人主页：杯咖啡
💡进步是今天的活动，明天的保证！
✨目前正在学习：SSM框架,算法刷题
🙌牛客网，刷算法过面试的神级网站，用牛客你也牛。 👉免费注册和我一起学习刷题👈
🐳希望大家多多支持🥰一起进步呀！

😎Love is the one thing we're capable of perceing that transcends time and space.
爱是我们唯一能够感知的可以超越时空维度的事物。

✨今日三剑

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

@[TOC]

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);
        }
    }
}

在这里插入图片描述