【算法】递归解决各种数据结构的遍历问题

2023-06-12 19:29| 来源: 网络整理| 查看: 265

文章目录前言递归输出树逆序输出栈递归逆序输出链表递归判断字符串是否是回文串

前言

对于递归算法，我们最先想到的应该就是用递归的方式去中序遍历一棵树，递归的使用使得我们可以先深入到下层中，然后慢慢的输出下层的元素之后输出上层元素。因此，基于此，我们甚至可以使用递归来逆序输出一个栈，链表等数据结构。

递归输出树

使用递归输出树

逆序输出栈

使用递归逆序输出一个栈的内容

递归逆序输出链表

与上面逆序输出一个栈差不多，我们可以设定输出链表内容的条件，我们可以先让链表不断的向内遍历，遍历到尾节点没有下一个节点了，我们才开始输出链表的内容，那么就可以做到逆序输出链表的内容了。

public void reverseList(ListNode head){ if(head!=null){ reverseList(head.next); System.out.println(head.val); } }

基于这种方式，我们甚至可以使用递归来判断一个链表是不是回文链表。

currentNode 指针是先到尾节点，由于递归的特性再从后往前进行比较。frontPointer 是递归函数外的指针。若 currentNode.val != frontPointer.val 则返回 false。反之，frontPointer 向前移动并返回 true。

算法的正确性在于递归处理节点的顺序是相反的（回顾上面打印的算法），而我们在函数外又记录了一个变量，因此从本质上，我们同时在正向和逆向迭代匹配。

计算机在递归的过程中将使用堆栈的空间，这就是为什么递归并不是 O(1) 的空间复杂度。

package com.leetcode.learn.list.easy; import com.leetcode.learn.list.ListNode; /** * @author: 张锦标 * @date: 2023/6/10 11:15 * PalindromeList类 */ public class PalindromeList { private ListNode frontPointer; private boolean recursivelyCheck(ListNode currentNode) { if (currentNode != null) { if (!recursivelyCheck(currentNode.next)) { return false; } if (currentNode.val != frontPointer.val) { return false; } frontPointer = frontPointer.next; } return true; } public boolean isPalindrome(ListNode head) { frontPointer = head; return recursivelyCheck(head); } //public boolean isPalindrome(ListNode head){ // StringBuilder sb = new StringBuilder(); // ListNode temp = head; // while(temp!=null){ // sb.append(temp.val); // temp=temp.next; // } // return sb.toString().equals(sb.reverse().toString()); //} public void reverseList(ListNode head){ if(head!=null){ reverseList(head.next); System.out.println(head.val); } } } 递归判断字符串是否是回文串

使用递归的方式，我们也可以用来判断一个字符串是否是回文串。我们可以将字符串按照中心划分两半，使用两个指针分别指向字符串的开头和末尾然后向中间遍历。不断判断这两个指针是否相同，如果是，那么指针向中间继续移动。

package com.leetcode.learn.string; /** * @author: 张锦标 * @date: 2023/6/10 11:44 * RecusionHuiwen类 * 使用递归的方式来判断一个字符串是否是回文串 */ public class RecusionHuiwen { public static boolean isPalindrome(String s,int n,int m){ if (m //判断当前两个对称位置是否相同 return isPalindrome(s,n+1,m-1); //相同继续向后遍历递归 } return false; } public static void main(String[] args) { String s = "abccba"; System.out.println(isPalindrome(s, 0, s.length())); } }

【本文地址】

公司简介

联系我们