動態規劃、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都可以用于解決二叉樹問題，但它們各自關聯。
)
