动态规划、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都可以用于解决二叉树问题，但它们各自关联。