共计 4346 个字符，预计需要花费 11 分钟才能阅读完成。
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;
}
}
