递归算法还有哪些是你不知道的----【探讨Java经典遍历问题和面试题】

简介: 递归算法还有哪些是你不知道的----【探讨Java经典遍历问题和面试题】

作为一名对技术充满热情的学习者,我一直以来都深刻地体会到知识的广度和深度。在这个不断演变的数字时代,我远非专家,而是一位不断追求进步的旅行者。通过这篇博客,我想分享我在某个领域的学习经验,与大家共同探讨、共同成长。请大家以开放的心态阅读,相信你们也会在这段知识之旅中找到启示。



前言

对于学习编程的同学来说,可能最先接触到的就是遍历算法,但是对于新手来说,如何正确理解遍历以及如何在适当的场合使用遍历,让你的代码变得更加简洁高效是个难以解决问题,下面我们就来好好的聊聊我们熟知而不善使用的递归


一、如何理解递归

理解递归的关键是将大问题分解为小问题,并相信这些小问题的解决方法是正确的。在递归算法中,你可以将问题定义为基本情况和递归情况。基本情况是问题可以直接解决的最小情况,而递归情况则是通过调用自身来解决规模较小但相似的问题。通过这种方式,你逐步解决问题,直到达到基本情况。

例如,考虑计算阶乘的问题。递归地,你可以将计算n的阶乘的问题转化为计算(n-1)的阶乘,一直递归下去,直到n等于1时,就是基本情况,阶乘为1。

二、递归的使用及注意事项

在以下情况中我们是建议使用递归的:

1.问题具有自相似的结构: 当问题可以被分解为规模较小、结构相似的子问题时,递归可以更自然地表达解决方法。

2.树状结构问题: 递归在处理树状结构(如树、图)的问题时非常有用,因为树的节点通常具有相似的属性。

3.分治法: 递归常用于分治法,其中问题被分成若干个相互独立的子问题,然后递归地解决这些子问题。

4.动态规划: 在某些动态规划问题中,递归可以用来建立问题的递归关系,但需要谨慎处理重叠子问题以提高效率。

使用递归时需要注意以下几点:

1.基准情况: 确保定义了递归的基准情况,以防止无限递归。基准情况是递归的结束条件,确保它能够最终被满足。

2.递归深度: 避免递归深度过大,以免导致堆栈溢出。在处理大规模问题时,考虑使用迭代或其他优化方法。

3.重叠子问题: 在使用递归解决动态规划问题时,注意避免重复计算相同的子问题,以提高效率。可以使用记忆化技术或迭代的动态规划方法。

4.性能问题: 递归可能导致性能开销,特别是在调用层数较多的情况下。在需要追求效率的情况下,可能需要考虑迭代或其他非递归方法。

5.清晰性和可读性: 递归的代码结构应当清晰易懂,避免过度复杂化。适当的注释和命名有助于提高代码的可读性。

我就不过多介绍,只需要注意就好,初学者了解即可,后面我们会深度学习递归的底层

三、Java中的遍历经典问题

在Java中,递归经常用于解决需要重复执行相似操作的问题。以下是一些常见的用途:

树结构遍历: 遍历树形结构,如二叉树,可以通过递归来实现。每次递归访问一个节点,并在子树上重复这一过程。

class TreeNode {
    int val;
    TreeNode left, right;
    // ...
}
void traverseTree(TreeNode node) {
    if (node != null) {
        // 处理当前节点
        // 递归处理左子树
        traverseTree(node.left);
        // 递归处理右子树
        traverseTree(node.right);
    }
}

阶乘计算: 如前所述,计算阶乘是递归的经典例子。

int factorial(int n) {
    if (n == 0 || n == 1) {
        return 1; // 基本情况
    } else {
        return n * factorial(n - 1); // 递归情况
    }
}

问题拆解: 一些问题可以通过不断拆解为子问题来解决,例如归并排序等。

在Java中,遍历二叉树通常使用递归或迭代的方式,包括前序遍历、中序遍历和后序遍历。下面分别展示了这三种遍历的递归实现

1.前序遍历(Preorder Traversal):

访问当前节点

递归遍历左子树

递归遍历右子树

class TreeNode {
    int val;
    TreeNode left, right;
    // ...
}
void preorderTraversal(TreeNode node) {
    if (node != null) {
        System.out.print(node.val + " "); // 访问当前节点
        preorderTraversal(node.left);     // 递归遍历左子树
        preorderTraversal(node.right);    // 递归遍历右子树
    }
}

2.中序遍历(Inorder Traversal):

递归遍历左子树

访问当前节点

递归遍历右子树

void inorderTraversal(TreeNode node) {
    if (node != null) {
        inorderTraversal(node.left);     // 递归遍历左子树
        System.out.print(node.val + " "); // 访问当前节点
        inorderTraversal(node.right);    // 递归遍历右子树
    }
}

3.后序遍历(Postorder Traversal):

递归遍历左子树

递归遍历右子树

访问当前节点

void postorderTraversal(TreeNode node) {
    if (node != null) {
        postorderTraversal(node.left);   // 递归遍历左子树
        postorderTraversal(node.right);  // 递归遍历右子树
        System.out.print(node.val + " "); // 访问当前节点
    }
}

四、如何在Java中解决汉诺塔问题

汉诺塔问题是一个经典的递归问题,可以通过递归来解决。在汉诺塔问题中,有三根柱子(A、B、C),A柱上有n个不同大小的圆盘,按照从上到下递增的顺序。目标是将所有圆盘从A柱移动到C柱,可以借助B柱作为辅助。

以下是用递归解决汉诺塔问题的Java代码:

class HanoiTower {
    // 移动圆盘的函数
    void moveDisk(int n, char source, char target, char auxiliary) {
        if (n == 1) {
            // 当只有一个圆盘时,直接移动到目标柱子
            System.out.println("Move disk 1 from " + source + " to " + target);
        } else {
            // 将n-1个圆盘从源柱移动到辅助柱
            moveDisk(n - 1, source, auxiliary, target);
            
            // 移动第n个圆盘到目标柱
            System.out.println("Move disk " + n + " from " + source + " to " + target);
            
            // 将n-1个圆盘从辅助柱移动到目标柱
            moveDisk(n - 1, auxiliary, target, source);
        }
    }
    public static void main(String[] args) {
        HanoiTower hanoiTower = new HanoiTower();
        int numberOfDisks = 3; // 设置圆盘数量
        hanoiTower.moveDisk(numberOfDisks, 'A', 'C', 'B');
    }
}

此代码演示了如何使用递归函数 moveDisk 解决汉诺塔问题。

五、Java遍历经典面试题

找出二叉树中两个节点的最低公共祖先(Lowest Common Ancestor):

  • 问题: 怎样找出二叉树中两个节点的最低公共祖先?
  • 解释: 使用递归,从根节点开始遍历,如果当前节点为null或等于其中一个目标节点,则返回该节点。否则,递归查找左右子树。

下面是Java中的详细代码解释和底层逻辑:

class TreeNode {
    int val;
    TreeNode left, right;
    // ...
}
public class LowestCommonAncestor {
    public TreeNode findLowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root; // 当前节点为null或是目标节点之一,直接返回当前节点
        }
        // 递归查找左右子树
        TreeNode left = findLowestCommonAncestor(root.left, p, q);
        TreeNode right = findLowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root; // 左右子树各包含一个目标节点,当前节点即为最低公共祖先
        } else if (left != null) {
            return left; // 左子树包含目标节点,返回左子树的结果
        } else {
            return right; // 右子树包含目标节点,返回右子树的结果
        }
    }
    public static void main(String[] args) {
        // 创建二叉树
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        LowestCommonAncestor lca = new LowestCommonAncestor();
        
        // 寻找节点5和节点1的最低公共祖先
        TreeNode result = lca.findLowestCommonAncestor(root, root.left, root.right);
        System.out.println("Lowest Common Ancestor: " + result.val); // 预期输出:3
    }
}

这段代码通过递归方式查找最低公共祖先。如果当前节点为null或等于其中一个目标节点,则直接返回当前节点。然后,递归查找左右子树,如果左右子树各包含一个目标节点,当前节点即为最低公共祖先。如果只有一个子树包含目标节点,则返回该子树的结果。这个递归过程最终会回溯到找到最低公共祖先。


总结

当然,对于遍历的总结远不止于此,遍历算法最重要的是让同学们有大问题化为小问题的思想,面对大量的代码循环时,能够抓住问题的根本,用一种方法来解决问题。在遍历算法构建的同时,更应该注重效率,想到更好的算法的情况下,大家还是尽量使用别的方法,实在解决不了在尝试使用遍历。我们需要关注遍历带来的其他不利的影响,别面出现堆栈溢出

感谢大家抽出宝贵的时间来阅读博主的博客,新人博主,感谢大家关注点赞,祝大家未来的学习工作生活一帆风顺,加油!!!

目录
相关文章
|
6天前
|
负载均衡 算法 应用服务中间件
面试题:Nginx有哪些负载均衡算法?Nginx位于七层网络结构中的哪一层?
字节跳动面试题:Nginx有哪些负载均衡算法?Nginx位于七层网络结构中的哪一层?
25 0
|
11天前
|
算法
【算法与数据结构】二叉树(前中后)序遍历2
【算法与数据结构】二叉树(前中后)序遍历
|
18天前
|
存储 算法 Java
Java数据结构与算法-java数据结构与算法(二)
Java数据结构与算法-java数据结构与算法
58 1
|
6天前
|
Java 关系型数据库 MySQL
大厂面试题详解:Java抽象类与接口的概念及区别
字节跳动大厂面试题详解:Java抽象类与接口的概念及区别
30 0
|
13天前
|
搜索推荐 Java
Java排序算法
Java排序算法
|
13天前
|
搜索推荐 Java
Java基础(快速排序算法)
Java基础(快速排序算法)
|
16天前
|
存储 缓存 算法
Java入门高频考查基础知识4(字节跳动面试题18题2.5万字参考答案)
最重要的是保持自信和冷静。提前准备,并对自己的知识和经验有自信,这样您就能在面试中展现出最佳的表现。祝您面试顺利!Java 是一种广泛使用的面向对象编程语言,在软件开发领域有着重要的地位。Java 提供了丰富的库和强大的特性,适用于多种应用场景,包括企业应用、移动应用、嵌入式系统等。下是几个面试技巧:复习核心概念、熟悉常见问题、编码实践、项目经验准备、注意优缺点、积极参与互动、准备好问题问对方和知其所以然等,多准备最好轻松能举一反三。
46 0
Java入门高频考查基础知识4(字节跳动面试题18题2.5万字参考答案)
|
16天前
|
存储 算法 JavaScript
Java入门高频考查算法逻辑基础知识3-编程篇(超详细18题1.8万字参考编程实现)
解决这类问题时,建议采取下面的步骤: 理解数学原理:确保你懂得基本的数学公式和法则,这对于制定解决方案至关重要。 优化算法:了解时间复杂度和空间复杂度,并寻找优化的机会。特别注意避免不必要的重复计算。 代码实践:多编写实践代码,并确保你的代码是高效、清晰且稳健的。 错误检查和测试:要为你的代码编写测试案例,测试标准的、边缘情况以及异常输入。 进行复杂问题简化:面对复杂的问题时,先尝试简化问题,然后逐步分析和解决。 沟通和解释:在编写代码的时候清晰地沟通你的思路,不仅要写出正确的代码,还要能向面试官解释你的
32 0
|
18天前
|
XML 存储 算法
Java数据结构与算法-java数据结构与算法(五)
Java数据结构与算法-java数据结构与算法
47 0
|
20天前
|
Java 程序员 API
java1.8常考面试题
在Java 1.8版本中,引入了很多重要的新特性,这些特性常常成为面试的焦点
41 8