当前位置： 首页 > article >正文

递归、搜索与回溯算法 - 1 （ 递归 二叉树 8000 字详解 ）

article 2024/11/22 18:42:15

一：递归

1.1 汉诺塔

题目链接：汉诺塔

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

class Solution {
    
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A, A.size(), B, C);
    }

    // a 是源柱，b 是辅助柱，c 是目的柱,把 a 柱上的 n 个元素借助 b 柱放在 c 住上
    public void dfs(List<Integer> a, int n, List<Integer> b, List<Integer> c){
        // 递归出口
        if(n == 1){
            int t = a.size();
            Integer tmp = a.remove(t - 1); // 获取最后一个元素的同时还要移除，所以用 remove
            c.add(tmp);
            return; // 当 n == 1 时开始函数的归过程
        }

        dfs(a, n - 1, c, b); // 开始函数的递归过程

        int t = a.size();
        Integer tmp = a.remove(t - 1); // 获取最后一个元素的同时还要移除，所以用 remove
        c.add(tmp);

        dfs(b, n - 1, a, c); // 开始函数的递归过程
    }
}

在这里插入图片描述

class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        for(int x :A) C.add(x);
    }
}

在这里插入图片描述

1.2 合并两个有序链表

题目链接：合并两个有序链表

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /**
     * 合并两个有序链表，让新链表也有序
     * @param list1 第一个升序链表的头节点
     * @param list2 第二个升序链表的头节点
     * @return 合并后的升序链表的头节点
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 函数的出口
        if(list1 == null) return list2;
        if(list2 == null) return list1;

        // 重复子问题
        if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next,list2);
            return list1; // 返回经过 mergeTwoLists 作用后的有序列表和 list1 较小节点合并后的有序列表
        }else{
            list2.next = mergeTwoLists(list1,list2.next);
            return list2;
        }
    }
}

在这里插入图片描述

1.3 反转链表

题目链接：反转链表

在这里插入图片描述
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
     /**
     * 反转以 head 为起点的子链表，返回反转后的头节点
     * @param head 单链表的头节点
     * @return 反转后的单链表的头节点
     */
    public ListNode reverseList(ListNode head) {
        // 先处理两个特殊情况，一个是 head 为空，一个是 head 只有一个元素，这两种情况下都不用进行逆序
        if(head == null || head.next == null) return head;

        // 重复子问题
        ListNode newNode = reverseList(head.next); // reverseList 返回头节点是为了我们能直接把返回值返回给程序，虽然这个头节点在递归中没啥用
        head.next.next = head;
        head.next = null;
         
        return newNode;
    }
}

在这里插入图片描述

1.4 两两交换链表中的结点

题目链接：两两交换链表中的结点

在这里插入图片描述
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
     /**
     * 两两交换链表中的节点（递归实现）
     * @param head 链表的头节点
     * @return 交换后的链表的头节点
     */
    public ListNode swapPairs(ListNode head) {
        // 先处理 head 只有为空和 head 只有一个元素的情况
        if(head == null || head.next == null) return head;

        // 接下来就是重复子问题了，先获取一下逆置后的头节点，用于返回
        ListNode tmp = swapPairs(head.next.next);
        ListNode swap = head.next; // swap 是 head 的下一个节点
        swap.next = head;
        head.next = tmp;

        return swap; // 返回交换后的头节点

    }
}

在这里插入图片描述

1.5 Pow(x, n) - 快速幂

题目链接：Pow(x, n) - 快速幂

在这里插入图片描述
在这里插入图片描述

class Solution {
    public double myPow(double x, int n) {
        // 如果 n < 0，计算 1.0 / (x 的 -n 次幂)；否则直接计算 x 的 n 次幂
        return n < 0 ? 1.0 / pow(x, -n) : pow(x, n);
    }

    /**
     * 快速幂的递归实现
     * @param x 底数
     * @param n 指数（非负整数）
     * @return 计算结果 x 的 n 次幂
     */
      public double pow(double x, int n){
        // 递归函数的出口
        if(n == 0) return 1.0;

        // 递归求解 x 的 n/2 次幂
        double tmp = pow(x, n / 2);
        return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
      }
}

在这里插入图片描述

二：二叉树

2.1 计算布尔二叉树的值

题目链接：计算布尔二叉树的值
在这里插入图片描述
在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * 递归方法评估二叉布尔树的值
     * @param root 二叉布尔树的根节点
     * @return 二叉布尔树的布尔值结果
     */
    public boolean evaluateTree(TreeNode root) {
        // 函数的出口，因为二叉树是完整的二叉树，所以我们只需要判断左子树是否为空即可
        if(root.left == null) return root.val == 1 ? true : false;

        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);

        return root.val == 2 ? left || right : left && right;

    }
}

在这里插入图片描述

2.2 求根节点到叶节点数字之和

题目链接：求根节点到叶节点数字之和

在这里插入图片描述
在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumNumbers(TreeNode root){
        // 调用深度优先搜索（DFS）方法，初始路径和 preSum 为 0
        return dfs(root, 0);
    }

     /**
     * 深度优先搜索（DFS）方法
     * @param root 当前节点
     * @param preSum 从根节点到当前节点路径组成的数字
     * @return 从当前节点到所有叶子节点路径组成的数字之和
     */
    public int dfs(TreeNode root, int preSum){
        preSum = preSum * 10 + root.val;
        if(root.left == null && root.right == null) return preSum;

        int ret = 0;
        if (root.left != null) ret += dfs(root.left, preSum);
        if (root.right != null) ret += dfs(root.right, preSum);

        return ret;
    }
}

在这里插入图片描述

2.3 二叉树剪枝

题目链接：二叉树剪枝

在这里插入图片描述
在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
     /**
     * 给定一个二叉树，如果一个节点的值为 0，且其所有子树都被修剪为空，则该节点也需要被修剪。
     * 最终返回修剪后的二叉树。
     * @param root 二叉树的根节点
     * @return 修剪后的二叉树的根节点
     */
    public TreeNode pruneTree(TreeNode root) {
        // 递归出口
        if(root == null) return null;

        // 如果不为空就递归遍历左右子树
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);

        if(root.left == null && root.right == null && root.val == 0) root = null; // 如果左右子树递归后变为空了，并且当前节点的值也为 0 ，那么就返回空，否则返回这个树的头节点

        return root;
    }
}

在这里插入图片描述

2.4 验证二叉搜索树

题目链接：验证二叉搜索树

在这里插入图片描述

在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 定义一个全局变量，用于记录上一个访问的节点值
    long prev = Long.MIN_VALUE;

    /**
     * 验证二叉搜索树的有效性
     * @param root 二叉树的根节点
     * @return 如果是有效的二叉搜索树，返回 true；否则返回 false
     */
    public boolean isValidBST(TreeNode root) {
        // 递归出口：如果节点为空，返回 true，叶子节点天然是一个搜索二叉树
        if (root == null) return true;

        // 递归验证左子树是否为有效的二叉搜索树
        boolean left = isValidBST(root.left);
        // 剪枝：如果左子树不是有效的二叉搜索树，直接返回 false
        if (left == false) return false;

        // 判断当前节点的值是否大于上一个访问的节点值
        boolean cur = false;
        if (root.val > prev) cur = true;
        if (cur == false) return false;  // 如果当前节点值不满足条件，返回 false,否则更新 prev 的值
        else  prev = root.val;


        // 递归验证右子树是否为有效的二叉搜索树
        boolean right = isValidBST(root.right);

        //右子树的递归调用依赖于当前节点的合法性。如果当前节点不合法，递归自然不会进入右子树，等价于隐式剪枝。
        // 只有当左子树、当前节点、右子树均有效时，才返回 true
        return left && cur && right;
    }
}

在这里插入图片描述

2.5 二叉搜索树中第 K 小的元素

题目链接：二叉搜索树中第 K 小的元素

在这里插入图片描述
在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 先定义两个全局变量，count 用来记录遍历的节点个数，ret 存储最终结果
    int count, ret;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        bfs(root);
        return ret;
    }

    public void bfs(TreeNode root){
        // 递归的出口
        if(root == null) return;

        // 接下来开始左中右的遍历
        bfs(root.left);
        
        // 因为给出的 root 一定是一个二叉搜索数，所以中的过程我们直接让 count-- 即可
        count--;
        if(count == 0){
            ret = root.val;
            return;
        } 

        bfs(root.right);
    }
}

在这里插入图片描述

2.6 二叉树的所有路径

题目链接：二叉树的所有路径

在这里插入图片描述
在这里插入图片描述

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 用 ret 存储最终的结果
    List<String> ret;

    public List<String> binaryTreePaths(TreeNode root) {
        ret = new ArrayList<>();
        dfs(root, new StringBuffer());
        return ret;
    }

     /**
     * 深度优先搜索方法，用于遍历二叉树并生成路径
     * @param root 当前节点
     * @param _path 当前路径（到达当前节点时的路径）
     */
    void dfs(TreeNode root, StringBuffer _path){
        // 第一步，先拼接上这个节点的值
        StringBuffer path = new StringBuffer(_path); // 要根据传入的 _path 构造 path
        path.append(Integer.toString(root.val));

        // 接下来判断一下是不是叶子节点，如果是叶子节点的话就不用加上 -> 了，直接把 pagth 保存在 ret 中并返回
        if(root.left == null && root.right == null){
            ret.add(path.toString());
            return;
        }else{
            path.append("->");
        }

        // 接着继续去左子树和右子树继续找路径
        if (root.left != null) dfs(root.left, path);
        if (root.right != null) dfs(root.right, path);
    }
}

在这里插入图片描述

三：穷举 vs 深搜

3.1 全排列

题目链接：全排列

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

class Solution {
    // 先定义三个全局变量，ret 用来存储最终结果，path 用来记录路径，check 用来判断某个数字是否被使用
    List<List<Integer>> ret;
    List<Integer> path;
    boolean[] check;

    public List<List<Integer>> permute(int[] nums){
        // 先初始化一下三个全局变量
        ret = new ArrayList<>();
        path = new ArrayList<>();
        check = new boolean[nums.length]; // check 的长度要和 nums 数组的长度一样，这样才能保证每个数字都存在于 check 中

        dfs(nums);
        return ret;
    }

     /**
     * 深度优先搜索方法，生成所有排列
     * @param nums 输入的整数数组
     */
    public void dfs(int[] nums){
        // 递归的出口
        if(path.size() == nums.length){
            ret.add(new ArrayList(path));
            return;
        }

        // 接着只关注某一个子问题
        for(int i = 0; i < check.length; i++){
            // 如果当前的数字没有被使用的话，就把这个数字放在 path 中
            if(check[i] == false){
                path.add(nums[i]);
                check[i] = true;

                dfs(nums);

                // 在函数归的过程时，要把 path 中最后一个元素弄掉，并把 check 中的元素置为 false
                 check[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}

在这里插入图片描述

3.2 子集

题目链接：子集

在这里插入图片描述

class Solution {
    // 先定义两个全局变量，ret 用于存储最终的结果，path 用于记录路径
    List<List<Integer>> ret;
    List<Integer> path;

    public List<List<Integer>> subsets(int[] nums){
        // 先初始化一下两个全局变量
        ret = new ArrayList<>();
        path = new ArrayList<>();

        dfs(nums, 0);
        return ret;
    }

     /**
     * 深度优先搜索方法，生成所有子集
     * @param nums 输入的整数数组
     * @param pos 从哪开始枚举，比如说 1， 2， 3
     */
    public void dfs(int[] nums, int pos){
        // 首先先把当前层次的 path 加入到 ret 中
        ret.add(new ArrayList(path));

        // 接着开始把 pos 后面的数字后加到 path 中
        for(int i = pos; i < nums.length; i++){
            path.add(nums[i]);

            // 接着继续把这个数字往深处递归
            dfs(nums, i + 1);

            // 回溯，把最后一个元素移除
            path.remove(path.size() - 1);
        }
    }
}

在这里插入图片描述


http://www.kler.cn/a/404677.html

相关文章：

  • 面试小结（一）
  • 手机领夹麦克风哪个牌子好，哪种领夹麦性价比高，热门麦克风推荐
  • 【Golang】协程
  • 在应用启动时，使用 UniApp 提供的 API 检查和请求权限。
  • o1的风又吹到多模态，直接吹翻了GPT-4o-mini
  • 单元测试框架gtest学习（三）—— 事件机制
  • STM32完全学习——使用SysTick精确延时（阻塞式）
  • 模拟实现STL中的list
  • 第三十六章 docker image 本地导出 导入
  • Spring Security Granted Authority（授予权限）
  • Android7点开语言直接显示语言偏好设置
  • pycharm调试transformers(hugging face)的模型
  • day03（单片机高级）RTOS
  • el-table根据指定字段合并行和列+根据屏幕高度实时设置el-table的高度
  • async在js中是强制同步的意思吗
  • 无人机的激光雷达避障系统阐述！
  • vmware虚拟机给创建的centos扩展磁盘步骤
  • 【MySQL实战45讲笔记】基础篇——深入浅出索引（上）
  • 利用代理IP爬取Zillow房产数据
  • 实时多模态 AI 的 N 种新可能丨实时互动和大模型专场@RTE2024回顾
  • C++学习——编译的过程
  • 【软考】系统架构设计师-信息系统基础
  • 1.1 爬虫的一些知识（大模型提供语料）
  • 渗透测试学习笔记—shodan（1）
  • Flink错误：一historyserver无法启动，二存在的文件会报错没有那个文件或目录
  • 乐鑫芯片模组物联网方案，智能设备升级新选择，启明云端乐鑫代理商