二叉樹路徑問題
二叉樹路徑問題主要是集中在查找二叉樹路徑契沫、計算路徑和之類的問題，個人理解是在二叉樹遍歷的基礎上不斷加鹽升級的問題誉券。本文為個人筆記桂塞，主要總結(jié)歸納二叉樹路徑相關的問題。
二叉樹的所有路徑
［力扣２５７,二叉樹的所有路徑］(https://leetcode-cn.com/problems/binary-tree-paths/),比較簡單只在二叉樹遍歷的基礎上增加了記錄路徑的要求凉逛，關鍵點在于到達葉子節(jié)點的時候記錄路徑好性宏。方法簽名如下：
public List binaryTreePaths(TreeNode root){}
遍歷的模板迭代或遞歸，參考算法筆記之二叉樹遍歷状飞。
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<String> list = new ArrayList<>();
binaryTreePathsHelper(root, list, "");
return list;
}
private void binaryTreePathsHelper(TreeNode root, List<String> list, String origin) {
if (root == null) {
return;
}
StringBuilder stringBuilder = new StringBuilder(origin).append(root.val);
if (root.left == null && root.right == null) {
list.add(stringBuilder.toString());
} else {
String str = stringBuilder.append("->").toString();
binaryTreePathsHelper(root.left, list, str);
binaryTreePathsHelper(root.right, list, str);
}
}
}
路徑總和
路徑總和的問題要求是給出一個樹節(jié)點和和一個值判斷毫胜，判斷路徑總和有沒有和他相等的。詳情參考本題在找到所有路徑的基礎上增加要求判斷目標路徑和的存在性诬辈。使用簡單的遞歸迭代即可解決問題酵使。
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null){
return false;
}
if(root.left == null && root.right == null){
return root.val == targetSum;
}
boolean lResult = hasPathSum(root.left,tagetSum - root.val);
if(lResult){
return true;
}
return hasPathSum(root.right,tagetSum - root.val);
}
從葉子節(jié)點開始的最小字符串
類似路徑總和，加了對值的處理和保存焙糟。力扣問題詳情
String res = null;
public String smallestFromLeaf(TreeNode root) {
if (root == null) {
throw new IllegalArgumentException("參數(shù)異常");
}
smallestFromLeafHelper(root, new StringBuilder());
return res;
}
private void smallestFromLeafHelper(TreeNode root, StringBuilder str) {
if (root == null) {
return;
}
//做出選擇
str.insert(0, (char) (root.val + 97));
//判斷
if (root.left == null && root.right == null) {
String s = str.toString();
if (res == null || s.compareTo(res) < 0) {
res = s;
}
} else {
smallestFromLeafHelper(root.left, str);
smallestFromLeafHelper(root.right, str);
}
//撤銷選擇
str.delete(0, 1);
}
路徑總和 II
繼續(xù)加鹽口渔，二叉樹的路徑找到了之后也能判斷目標路徑總和是否存在，我又想在路徑集合中挑出和為指定值的路徑穿撮。詳情參考力扣112題搓劫。遞歸的問題都是具有回溯性的。參考labuladong大神給出的模板去解決此類問題做出選擇 -> 判斷選擇 -> 撤銷選擇混巧。
private int count = 0;
List<Integer> tmp = new ArrayList<>();
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> list = new ArrayList<>();
pathSumHelper(root, list, targetSum);
return list;
}
private void pathSumHelper(TreeNode root, List<List<Integer>> list, int targetSum) {
if (root == null) {
return;
}
//做出選擇
tmp.add(root.val);
count += root.val;
//判斷該選擇的是否滿足條件
if (root.left == null && root.right == null && count == targetSum) {
list.add(new ArrayList<>(tmp));
} else {
pathSumHelper(root.left, list, targetSum);
pathSumHelper(root.right, list, targetSum);
}
//撤銷選擇
tmp.remove(tmp.size() - 1);
count -= root.val;
}
路徑總和 III
路徑總和 III枪向，繼續(xù)加鹽，找出所有路徑總和為目標值的數(shù)量咧党，這次路徑的起點不限制為根秘蛔，終點也不限制葉子節(jié)點但是路徑的方向必須是向下的。
前綴和的方式：
int count = 0;
public int pathSum(TreeNode root, int sum) {
Map<Integer, Integer> prefixSumCount = new HashMap<>();//用于存放上層節(jié)點前綴和對應的個數(shù)
prefixSumCount.put(0, 1);//解決前綴和剛好為target的節(jié)點計數(shù)（包括兩種：例target = 8時，單節(jié)點[8] 或 [1,2,5]）
recursionPathSum(root, prefixSumCount, sum, 0);
return count;
}
private void recursionPathSum(TreeNode node, Map<Integer, Integer> prefixSumCount, int target, int currSum) {
if (node == null) {
return;
}
currSum += node.val;
//做出選擇并校驗選擇
count += prefixSumCount.getOrDefault(currSum - target, 0);
prefixSumCount.put(currSum, prefixSumCount.getOrDefault(currSum, 0) + 1);
//遞歸
recursionPathSum(node.left, prefixSumCount, target, currSum);
recursionPathSum(node.right, prefixSumCount, target, currSum);
//撤銷選擇
prefixSumCount.put(currSum, prefixSumCount.get(currSum) - 1);
}
/*純遞歸的方式時間復雜度較高深员，可以理解一下子問題的劃分
public int pathSum(TreeNode root, int targetSum) {
if (root == null) return 0;
int ret = pathSumStartWithRoot(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
return ret;
}
// 以root 為根節(jié)點的路徑和數(shù)量
private int pathSumStartWithRoot(TreeNode root, int sum) {
if (root == null) return 0;
int ret = 0;
if (root.val == sum) ret++;
ret += pathSumStartWithRoot(root.left, sum - root.val) + pathSumStartWithRoot(root.right, sum - root.val);
return ret;
}*/
基本模板是類似负蠕，復雜度均為O(n)。其中回溯的狀態(tài)值保存在散列表中倦畅，校驗的操作實際是分散了遮糖。處理邏輯很巧妙。
124. 二叉樹中的最大路徑和
繼續(xù)增加限制叠赐，以上的所有題目路徑的方向都是自上而下的∮耍現(xiàn)在不限制方向了，求二叉樹的最大路徑和芭概。題目一下子升級到困難級別赛不。
int maxSum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPathSumHelper(root);
return maxSum;
}
public int maxPathSumHelper(TreeNode root) {
if (root == null) {
return 0;
}
//為什么和0比較？要是最大和和比0還小那么這側(cè)就可以忽略了
int leftMaxSum = Math.max(maxPathSumHelper(root.left), 0);
int rightMaxSum = Math.max(maxPathSumHelper(root.right), 0);
//計算左根右的最大路徑和
maxSum = Math.max(maxSum, leftMaxSum + rightMaxSum + root.val);
//返回當前節(jié)點最大和（自上向下的方向）
return root.val + Math.max(leftMaxSum, rightMaxSum);
}
