动态规划、DFS 和回溯算法:二叉树问题的三种视角

这篇具有很好参考价值的文章主要介绍了动态规划、DFS 和回溯算法:二叉树问题的三种视角。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划、DFS 和回溯算法:二叉树问题的三种视角

在计算机科学中,算法是解决问题的核心。特别是对于复杂的问题,不同的算法可以提供不同的解决方案。在本篇博客中,我们将探讨三种算法:动态规划、深度优先搜索(DFS)和回溯算法,它们如何从不同的角度解决以二叉树为基础的问题。

二叉树问题的核心

二叉树是一种非常基础的数据结构,在许多算法问题中都会遇到。一个二叉树由节点和连接节点的边组成,每个节点最多有两个子节点。在解决二叉树问题时,我们通常需要考虑节点的值、树的结构、节点间的关系等因素。

动态规划

动态规划(Dynamic Programming, DP)是解决优化问题的一种方法。它将一个复杂问题分解成一系列子问题,并存储子问题的解,以避免重复计算。在二叉树问题中,动态规划通常关注整棵子树。

动态规划的关注点:子树

当我们使用动态规划解决二叉树问题时,我们通常从叶子节点开始,向上逐步构建解决方案。每个节点都代表了一个子问题的解,而这个解通常依赖于其子节点的解。通过这种方式,我们可以构建出整棵树的解。

例子:二叉树的最大路径和

假设我们要找到一棵二叉树中的最大路径和。在这个问题中,路径可以从任何节点开始,到任何节点结束,但必须沿着树的边行进。这是一个典型的可以用动态规划解决的问题。

我们可以为每个节点定义一个状态,表示“以该节点为根的子树中,从该节点出发的最大路径和”。然后,我们可以用递归的方式,从叶子节点向根节点递推,最终得到整棵树的最大路径和。

/**
     * 二叉树的直径
     * 给你一棵二叉树的根节点,返回该树的 直径 。
     *
     * 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
     *
     * 两节点之间路径的 长度 由它们之间边数表示。
     * @param root
     * @return
     */
    public int diameterOfBinaryTree(TreeNode root) {
        deep(root);
        return maxDeep - 1;
    }

    private int deep(TreeNode root){
        if(root==null){
            return 0;
        }
        int l = deep(root.left);

        int r = deep(root.right);

        maxDeep = Math.max(maxDeep,l+r+1);

        return 1 + Math.max(l, r);
    }

回溯算法

回溯算法是一种通过试错来找到所有/部分解决方案的算法。它的工作原理是逐步构建解决方案,并在发现当前解决方案无法成功时,取消上一步或几步的计算,再尝试其他可能的解决方案。

回溯算法的关注点:树枝

回溯算法在二叉树问题中关注的是“树枝”,即从根节点到叶子节点的路径。在构建解决方案的过程中,回溯算法会遍历这些路径,尝试所有的可能性,并在遇到死胡同时回退。

例子:二叉树的所有路径

例如,如果我们要找到一棵二叉树的所有根到叶子的路径,回溯算法就非常适合。我们从根节点开始,记录下路径,然后递归地探索左右子节点。如果到达叶子节点,就记录下完整的路径。如果递归返回,我们就撤销当前步骤,尝试其他选项。

List<List<Integer>> resultAll = new ArrayList<>();

    public List<List<Integer>> binaryTreePaths(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root != null) {
            result.add(root.val);
        }
        binaryTreePathsSub(root, result);
        return resultAll;
    }

    public void binaryTreePathsSub(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            resultAll.add(new ArrayList<>(result));
        }
        if (root.left != null) {
            result.add(root.left.val);
            binaryTreePathsSub(root.left, result);
            result.remove(result.size() - 1);
        }
        if (root.right != null) {
            result.add(root.right.val);
            binaryTreePathsSub(root.right, result);
            result.remove(result.size() - 1);
        }
    }

深度优先搜索(DFS)

深度优先搜索是一种用于遍历或搜索树或图的算法。DFS探索尽可能深的节点,并在必要时通过回溯来探索其他分支。

DFS的关注点:单个节点

DFS在二叉树问题中关注的是单个节点。它会尝试沿着一条路径深入到不能再深入为止,然后回溯到最近的分叉点,尝试其他路径。

例子:二叉树的深度

一个简单的例子是计算二叉树的最大深度。DFS可以从根节点开始,尽可能深地遍历每个分支,直到到达叶子节点。通过记录遍历过程中的最大深度,我们可以得到整棵树的最大深度。

/**
     * 二叉树的最大深度
     * @param root
     * @return
     */
    int maxDepth(TreeNode root) {
        traverse(root);
        return res;
    }

    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        deepth++;
        traverse(root.left);
        if (root.left == null && root.right == null) {
            res = Math.max(res, deepth);
        }
        traverse(root.right);
        deepth--;
    }

总结

虽然动态规划、回溯算法和DFS都可以用于解决二叉树问题,但它们各自关联。文章来源地址https://www.toymoban.com/news/detail-761082.html

到了这里,关于动态规划、DFS 和回溯算法:二叉树问题的三种视角的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法专题】二叉树中的深搜(DFS)

    深度优先遍历(DFS,全称为 Depth First Traversal),是我们树或者图这样的数据结构中常用的⼀种遍历算法。这个算法会尽可能深的搜索树或者图的分支,直到一条路径上的所有节点都被遍历完毕,然后再回溯到上一层,继续找⼀条路遍历。 在二叉树中,常见的深度优先遍历为

    2024年02月03日
    浏览(40)
  • 【算法】递归、回溯、剪枝、dfs 算法题练习(组合、排列、总和问题;C++)

    后面的练习是接着下面链接中的文章所继续的,在对后面的题练习之前,可以先将下面的的文章进行了解👇: 【算法】{画决策树 + dfs + 递归 + 回溯 + 剪枝} 解决排列、子集问题(C++) 思路 题意分析 :要求根据给出的数字,算出合法的括号组成个数。根据题目,我们可以总

    2024年02月22日
    浏览(48)
  • N皇后问题详解:回溯算法的应用与实践(dfs)

    题目如上图所示,在一个 n*n 的国际象棋棋盘上怎么摆放能使得皇后互相攻击不到(也就是在 任意一列、一行、一条对角线上都不存在两个皇后 ) 1.DFS 想要解决这个问题,我们可以使用dfs也就是 深度优先遍历 ,深度优先搜索的步骤为先递归到底再回溯上来,顾名思义,df

    2024年03月26日
    浏览(52)
  • 四大算法:贪心、分治、回溯、动态规划

    贪心算法(又称贪婪算法),在求解问题时,总是做出在当前看来是最好的选择。也就是说,不从整体最优解进行考虑,而是得到某种意义上的局部最优解。 贪心算法采用自顶向下,以迭代的方法做出贪心选择,每做一次贪心选择,就将所求问题简化为一个规模更小的问题。

    2024年02月15日
    浏览(60)
  • Offer必备算法08_二叉树dfs_六道力扣题详解(由易到难)

    目录 ①力扣2331. 计算布尔二叉树的值 解析代码 ②力扣129. 求根节点到叶节点数字之和 解析代码 ③力扣814. 二叉树剪枝 解析代码 ④​​​力扣98. 验证二叉搜索树 解析代码 ⑤力扣230. 二叉搜索树中第K小的元素 解析代码 ⑥力扣257. 二叉树的所有路径 解析代码 2331. 计算布尔二

    2024年03月18日
    浏览(40)
  • 算法 矩阵最长递增路径-(递归回溯+动态规划)

    牛客网: BM61 求矩阵的最长递增路径 解题思路: 1. 遍历二维矩阵每个位置,max求出所有位置分别为终点时的最长路径 2. 求某个位置为终点的最长路径时,使用动态规划dp对已经计算出的位置进行记录 3. 处理某个位置的最长路径时,如果dp[i][j]位置已有值,则直接返回即可,否则

    2024年02月07日
    浏览(41)
  • 动态规划 | 分治法 -- 所有可能的真二叉树

    给你一个整数  n  ,请你找出所有可能含  n  个节点的  真二叉树  ,并以列表形式返回。答案中每棵树的每个节点都必须符合  Node.val == 0  。 答案的每个元素都是一棵真二叉树的根节点。你可以按  任意顺序  返回最终的真二叉树列表 。 真二叉树  是一类二叉树,树中

    2024年04月16日
    浏览(27)
  • 0-1背包问题(动态规划+回溯法)

    给定n(n=100)种物品和一个背包。物品i的重量是wi(wi=100),价值为vi(vi=100),背包的容量为C(C=1000)。 应如何选择装入背包中的物品,使得装入背包中物品的总价值最大? 在选择装入背包的物品时,对每种物品i只有两个选择:装入或不装入。不能将物品i装入多次,也不能只装入部分

    2024年02月04日
    浏览(37)
  • 01背包(动态规划,贪心算法,回溯法,分支限界法)

    有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? number=4,capacity=8 物品编号(i) W(体积) V(价值) 1 2 3 2 3 4 3 4 5 4 5 6 1.什么是动态规划 1.动态规划算法是通过拆分问题,定义问题状态和状态之间的关系, 使得

    2024年02月08日
    浏览(67)
  • 五大常用算法——分治法,动态规划,回溯法,分支界限法,贪心算法

    (1) 分治法 将一个难以直接解决的大问题,分割成一些规模较小的相同问题 快速排序 快排也是分治的一个实例,快排每一趟会选定一个数,将比这个数小的放左面,比这个数大的放右面, 然后递归分治求解两个子区间,当然快排因为在分的时候就做了很多工作, 当全部分到

    2024年02月04日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包