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

阳光穿透心脏的1/2处 2024-03-16 16:09 31阅读 0赞

#### 文章目录 ####

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

## 前言 ##

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

## 递归输出树 ##

[使用递归输出树][Link 1]

## 逆序输出栈 ##

[使用递归逆序输出一个栈的内容][Link 2]

## 递归逆序输出链表 ##

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

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

[Link 1]: https://blog.csdn.net/Zhangsama1/article/details/130668399?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168636803716782427460029%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=168636803716782427460029&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-2-130668399-null-null.268%5Ev1%5Ekoosearch&utm_term=%E9%80%92%E5%BD%92&spm=1018.2226.3001.4450
[Link 2]: https://blog.csdn.net/Zhangsama1/article/details/130902054?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168636803716782427460029%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=168636803716782427460029&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-3-130902054-null-null.268%5Ev1%5Ekoosearch&utm_term=%E9%80%92%E5%BD%92&spm=1018.2226.3001.4450