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

前言

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

递归输出树

使用递归输出树

逆序输出栈

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

递归逆序输出链表

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

 public void reverseList(ListNode head){
        if(head!=null){
            reverseList(head.next);
            System.out.println(head.val);
        }
    }
1
2
3
4
5
6

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

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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

递归判断字符串是否是回文串

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

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<=1){ //递归结束条件
            return true;
        }else if(s.charAt(n)==s.charAt(m-1)){ //判断当前两个对称位置是否相同
            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()));
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25