03树结构深度优先搜索
# 02 树结构深度优先搜索
# 深度优先搜索简介
深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。
对于树结构而言，由于总是对新节点调用遍历，因此看起来是向着 深 的方向前进，或者说是垂直方向。考虑如下一颗简单的树，由4 个节点构成共三层，其 DFS 过程如下图所示：
我们从 0 号节点开始遍历，假如遍历顺序是从左子节点到右子节点，那么按照优先向着深的方向前进的策略，假如我们使用递归实现，我们的遍历过程为： 0（起始节点）->1（遍历更深一层的左子节点）->3（遍历更深一层的左子节点）->1（无子节点，返回父结点）->0（子节点均已完成遍历，返回父结点）->2（遍历更深一层的右子节点）->0（无子节点，返回父结点）-> 结束程序（子节点均已完成遍历）。如果我们使用栈实现，我们的栈顶元素的变化过程为 0->1->3->2。
DFS 的两种形式：
- 自上而下：把值通过参数的形式，从上往下传值；这种 DFS 形式一般自身不返回值，即函数返回值类型通常为
void - 自下而上：这是使用 DFS 最为常见的形式，即把子问题的解（或值）从下往上传，上层的递归层利用下层传递来的值计算当前层的解（或值），并继续向上传递；这种 DFS 形式都有返回值。这种形式的调用过程一般是 "V" 字型的，先逐层向下要子问题的解，然后从最小子问题开始逐层向上利用子问题的解构造当前问题解并向上传递，最终形成整体解。
树结构深度优先搜索编码模板：
// 先序遍历
void dfs(TreeNode* node){
if(!node){
return;
}
cout<<node->val;
dfs(node->left);
dfs(node->right);
}
// 中序遍历
void dfs(TreeNode* node){
if(!node){
return;
}
dfs(node->left);
cout<<node->val;
dfs(node->right);
}
// 后序遍历
void dfs(TreeNode* node){
if(!node){
return;
}
dfs(node->left);
dfs(node->right);
cout<<node->val;
}
# 104 二叉树的最大深度 (opens new window)
求一个二叉树的最大深度。
输入是一个二叉树，输出是一个整数，表示该树的最大深度。
输入： [3,9,20,null,null,15,7]，
3 / \ 9 20 / \ 15 7输出：3
解释：返回它的最大深度 3
解析：
采用深度优先搜索，其子问题是：假设左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为 max(l,r)+1。终止条件是访问的节点为空，推出递归。
class Solution {
public:
int maxDepth(TreeNode* root) {
if(!root){
return 0;
}
int l = maxDepth(root->left);
int r = maxDepth(root->right);
return max(l,r)+1;
}
};
# 110 平衡二叉树 (opens new window)
判断一个二叉树是否平衡。树平衡的定义是，对于树上的任意节点，其两侧节点的最大深度的差值不得大于 1。
输入是一个二叉树，输出一个布尔值，表示树是否平衡。
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
解析：
本题的思路类似104 二叉树的最大深度 (opens new window)，也是 DFS 的典型应用场景。不同的是在获取子树深度时要对当前左右子树的深度进行比较，如果还未遍历完二叉树就已经发现左右子树不平衡，则结束搜索直接返回 -1，避免再继续往下计算子树深度。
提前返回 -1 中断子树深度计算要注意的是：第一次返回 -1 的判断条件是 abs(left - right) > 1；但是在往上回溯深度计算结果的过程中，如果出现了中断，那么回溯结果为 -1，这时表明下层子树出现了不平衡情况，所以上层返回 -1 的判断条件是 left == -1 || right == -1。
class Solution {
public:
int treeDepth(TreeNode* root){
if(!root){
return 0;
}
int l = treeDepth(root->left);
int r = treeDepth(root->right);
if(l==-1 || r==-1 || abs(l-r)>1){
return -1;
}
return max(l,r)+1;
}
bool isBalanced(TreeNode* root) {
return treeDepth(root) != -1;
}
};
# 129 求根节点到叶节点数字之和 (opens new window)
给定一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。每条从根节点到叶节点的路径都代表一个数字，计算从根节点到叶节点生成的 所有数字之和。
输入一个二叉树，输出一个整数表示所有数字之和。
输入：root = [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
解析：
本题可以采用自上而下的递归，首先根据当前节点之前路径所代表的数字计算新路径所代表的数字，然后递归向下传播该结果找出二叉树中所有的数字，并计算和。
递推过程为：根据当前节点之前路径所代表的数字，计算加入当前节点后路径所代表的数字；当遍历到叶子节点时返回从根节点到该叶子节点所代表的数字；如果当前节点不是叶子节点则向左右子树递归计算路径所代表的数字，并计算以当前节点为根节点的子树的所有数字之和。
终止条件是访问的节点为空，推出递归。
class Solution {
public:
int dfs(TreeNode* root, int preSum){
if(!root){
return 0;
}
int sum = preSum*10 + root->val;
if(root->left == nullptr && root->right == nullptr){
return sum;
}else{
return dfs(root->left,sum)+dfs(root->right,sum);
}
}
int sumNumbers(TreeNode* root) {
return dfs(root,0);
}
};
# 113 路径总和 II (opens new window)
给定一个整数二叉树和一个目标值，找出所有 从根节点到叶子节点 路径总和等于给定目标值的路径。
输入一个二叉树和一个给定整数，输出一个二维数组，表示满足条件的所有路径。
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]
解析：
本题和129 求根节点到叶节点数字之和 (opens new window)相似，也可以采用自上而下的递归。
递推过程：自上而下递归遍历二叉树，每遍历一个节点，先将其加入当前路径并更新目标值为targetSum -= root->val；当遍历到叶子节点时，如果targetSum刚好等于 0，那么就找到了一条路径和为目标值的路径，将其加入结果集合。每遍完一个节点后，将其从当前路径中弹出，以便存储其他路径。
终止条件是访问的节点为空，推出递归。
class Solution {
private:
vector<vector<int>> res;
vector<int> path;
public:
void dfs(TreeNode* root, int targetSum){
if(!root){
return;
}
path.push_back(root->val);
targetSum -= root->val;
if(root->left==nullptr && root->right==nullptr && targetSum == 0){
res.push_back(path);
}
dfs(root->left,targetSum);
dfs(root->right,targetSum);
path.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
dfs(root,targetSum);
return res;
}
};
# 437 路径总和 III (opens new window)
给定一个整数二叉树，求有多少条路径节点值的和等于给定值。路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的。
输入一个二叉树和一个给定整数，输出一个整数，表示有多少条满足条件的路径。
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
解析：
本题和113 路径总和 II (opens new window)的区别在于路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径必须是由连续节点构成。所以本题可以在113题的基础上，递归过程中判断是否加入当前节点即可。
所以在递归遍历每个节点计算路径和过程中，需要分情况考虑：
- 如果选取该节点加入路径，则之后必须继续加入连续节点，或停止加入节点
- 如果不选取该节点加入路径，则对其左右节点进行重新进行考虑
我们需要一个计算路径和的辅助函数，用于计算以当前节点为根节点的子树中满足目标和的路径数量，该函数的实现思路与113题一致。
然后在主函数中递归遍历每个节点，并分别计算加入当前节点的满足目标值的路径数目和不加入当前节点的满足目标值的路径数目，两种情况之和即为二叉树中所有满足条件的路径数目。
class Solution {
public:
int pathWithRoot(TreeNode* root, int sum){
if(!root){
return 0;
}
int count = 0;
// 如果当前节点值与路径和一致则形成一条路径
if(root->val == sum){
count = 1;
}else{
count = 0;
}
// 往左右子节点继续寻找路径
count += pathWithRoot(root->left, sum-root->val);
count += pathWithRoot(root->right, sum-root->val);
return count;
}
int pathSum(TreeNode* root, int targetSum) {
if(!root){
return 0;
}
// 将当前节点加入路径
int ans = 0;
ans = pathWithRoot(root,targetSum);
// 不将当前节点加入路径，从左右子节点开始寻找新路径
ans += pathSum(root->left,targetSum);
ans += pathSum(root->right,targetSum);
return ans;
}
};
# 124 二叉树中的最大路径和 (opens new window)
给定一个二叉树，返回其最大路径和。路径指的是二叉树中任一节点到达另一节点的节点序列。
输入一个二叉树，输出一个整数表示最大路径和。
输入：root = [-10,9,20,null,null,15,7]
-10 / \ 9 20 / \ 15 7输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42
解析：
本题路径的定义和前面的不同，是指二叉树中任一节点到达另一节点的节点序列。所以本题不用考虑子树的情况，而是考虑计算二叉树中的一个节点的最大贡献值，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。
我们实现一个辅助函数 maxGain(node)用于计算节点的最大贡献值，该函数的递归计算过程如下：
空节点的最大贡献值等于 0
非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和，对于叶节点而言，最大贡献值等于节点值
class Solution {
private:
int maxSum = INT_MIN;
public:
int maxGain(TreeNode* root){
if(!root){
return 0;
}
int l = max(maxGain(root->left),0);
int r = max(maxGain(root->right),0);
int pathSum = root->val+l+r;
maxSum = max(maxSum,pathSum);
return root->val + max(l,r);
}
int maxPathSum(TreeNode* root) {
maxGain(root);
return maxSum;
}
};