LeetCode深度优先算法之树(门路相干)
树的问题个别都能够由深度优先算法和广度优先算法解决，门路相干的问题个别都能够用DFS或者基于DFS实现的回溯算法实现，咱们通过上面几道题来温习&训练DFS和回溯算法。
112.门路总和
形容
给定一个二叉树和一个指标和，判断该树中是否存在根节点到叶子节点的门路，这条门路上所有节点值相加等于指标和。
阐明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及指标和 sum = 22，
5 / \ 4 8 / / \ 11 13 4 / \ \ 7 2 1返回 true, 因为存在指标和为 22 的根节点到叶子节点的门路 5->4->11->2。
思路
首先，题目形容的是存在从根节点到叶子节点的门路，也就是须要先确定什么状况下遍历到了叶子节点了。依据题目形容，叶子节点指的是没有左右节点的节点。
if (node.left == null && node.right == null)sum的和与其判断的是节点的总和，所以这是一个累加的和。咱们须要记录每个节点的和，先记录后遍历子节点，这种场景就是dfs典型的场景。
addVal();recursion();dfs能够应用递归进行实现，目前曾经确定了能够应用dfs进行解决，递归的完结的条件是节点为null或者以后节点的左右节点为null。还有一个问题，咱们如何确定以后叶子节点累加的值等于目标值呢？
if sum == node1.val + node2.val + node3.val;then node3.val = sum - node2.val - node1.val; 所以咱们把子节点的目标值设置为sum - curNode.val,如果curNode.val = target的话，就代表存在一条从根节点到子节点的门路和等于目标值。
代码
class Solution { public boolean hasPathSum(TreeNode root, int sum) { if (root == null) return false; if (root.left == null && root.right == null) return sum == root.val; return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); }}113.门路总和II
题目形容
给定一个二叉树和一个指标和，找到所有从根节点到叶子节点门路总和等于给定指标和的门路。
阐明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及指标和 sum = 22，
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回:
[
[5,4,11,2],
[5,8,4,5]
]
思路
这道题是在112.门路总和的根底上扭转而来的，扭转的点是要记录所有和为目标值的门路。所以，这道题不能像112题那样满足条件后间接返回boolean类型，而是要全副遍历一遍直到满足条件为止，遇到这种穷举遍历判断是否满足指标条件的状况，能够应用回溯算法来解决这个问题。
回溯实质上也是DFS，只不过是回溯个别应用一个对象进行记录节点的值，当门路节点遍历实现后，而后节点最初的值，防止分支净化。
代码
class Solution { List<List<Integer>> res = new ArrayList<>(); public List<List<Integer>> pathSum(TreeNode root, int sum) { if (root == null) return res; List<Integer> list = new ArrayList<>(); this.backTrack(list, root, sum); return res; } void backTrack(List<Integer> list, TreeNode node, int sum) { if (node == null) return ; list.add(node.val); if (node.left == null && node.right == null) { if (node.val == sum) { res.add(new ArrayList<>(list)); } list.remove(list.size() - 1); return; } backTrack(list, node.left, sum - node.val); backTrack(list, node.right, sum - node.val); list.remove(list.size() - 1); }}129.求根到叶子节点数字之和
题目形容
给定一个二叉树，它的每个结点都寄存一个 0-9 的数字，每条从根到叶子节点的门路都代表一个数字。
例如，从根到叶子节点门路 1->2->3 代表数字 123。
计算从根到叶子节点生成的所有数字之和。
阐明: 叶子节点是指没有子节点的节点。
示例 1:
输出: [1,2,3] 1 / \ 2 3输入: 25解释:从根到叶子节点门路 1->2 代表数字 12.从根到叶子节点门路 1->3 代表数字 13.因而，数字总和 = 12 + 13 = 25.示例 2:输出: [4,9,0,5,1] 4 / \ 9 0 / \5 1输入: 1026解释:从根到叶子节点门路 4->9->5 代表数字 495.从根到叶子节点门路 4->9->1 代表数字 491.从根到叶子节点门路 4->0 代表数字 40.因而，数字总和 = 495 + 491 + 40 = 1026.思路
透过景象看实质，[1,2,3]这种状况下，咱们对应的后果是12+13=25。实际上，就是先记录左子树的值总和+右子树值总和，最初将总和值相加，这不就是后序遍历么。
recordValue();recursion(left);recursion(right);既然是后序遍历，实际上也就是DFS。咱们还有两个问题须要解决，第一是如果将以后节点的值进行累加，第二是递归的完结条件。
第一个问题，实际上curVal = preNum * 10 + node.val，递归过程中只有记录preNum的参数就好了，preNum的初始值就是0。
第二个问题就是递归的完结条件，其实就是遍历到叶子节点。叶子节点也就是左节点和右节点为空。
代码
class Solution { public int sumNumbers(TreeNode root) { if (root == null) return 0; return dfs(root, 0); } int dfs(TreeNode root, int preNum) { if (root == null) return 0; int num = preNum * 10 + root.val; if (root.left == null && root.right == null) return num; int leftSum = dfs(root.left, num); int rightSum = dfs(root.right, num); return leftSum + rightSum; }}257.二叉树的所有门路
题目形容
给定一个二叉树，返回所有从根节点到叶子节点的门路。阐明: 叶子节点是指没有子节点的节点。示例:输出: 1 / \2 3 \ 5输入: ["1->2->5", "1->3"]思路
所有门路问题第一想法就是回溯，然而这道题不同的是存在一个非凡的字符串->，回溯删除元素的时候要思考这种场景，所以在删除节点之前记录以后字符串的索引地位，这样就能够应用stringBuilder.deleteCharAt(index, cur.length());
代码
class Solution { List<String> res = new ArrayList<>(); public List<String> binaryTreePaths(TreeNode root) { if (root == null) return res; this.backTrack(new StringBuilder(""), root); return res; } public void backTrack(StringBuilder sb, TreeNode node) { if (node == null) return; if (node.left == null && node.right == null) { res.add(sb.toString() + node.val); return; } int delIndex = sb.length(); sb.append(node.val).append("->"); backTrack(sb, node.left); backTrack(sb, node.right); sb.delete(delIndex, sb.length()); }}程序员面试金典04.12 求和门路
题目形容
给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有门路的数量。留神，门路不肯定非得从二叉树的根节点或叶节点开始或完结，然而其方向必须向下(只能从父节点指向子节点方向)。
示例:
给定如下二叉树，以及指标和 sum = 22，
5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回:
3
解释：和为 22 的门路有：[5,4,11,2], [5,8,4,5], [4,11,7]
提醒：
节点总数 <= 10000
思路
这道题和下面题不同的是，门路不要求是从根节点开始遍历的。所以咱们须要记录每层节点的值，先通过递归算法确定树的深度，而后依据以后深度进行赋值，遍历以后深度对应值直到深度为0为止，如果遍历的和等于sum，那么数量+1
代码
class Solution { int res = 0; public int pathSum(TreeNode root, int sum) { if (root == null) return res; int depth = depth(root); int[] levels = new int[depth]; this.bfs(root, levels, 0, sum); return res; } void bfs(TreeNode root, int[] levels, int level, int num) { if (root == null) return; levels[level] = root.val; int sum = 0; for (int i = level; i >= 0; i--) { sum += levels[i]; if (sum == num) { res += 1; } } bfs(root.left, levels, level + 1, num); bfs(root.right, levels, level + 1, num); } int depth(TreeNode root) { if (root == null) return 0; int left = depth(root.left); int right = depth(root.right); return left > right ? left + 1 : right + 1; }}