二叉树路径问题

## 问题分类

二叉树路径的问题大致可以分为两类，分别是**自顶向下**和**非自顶向下**。

### 自顶向下

#### 概述

1. 自顶向下就是**从某一个节点**（不一定是根节点）**出发**，**从上向下寻找路径**，**到某一个节点**（不一定是叶节点）**结束**，继续细分的话，还可以分为**一般路径**和**定和路径**。
2. 这类题**通常用**[**深度优先搜索**](https://notebook.ricear.com/project-21/doc-724/#1-%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86%E7%AE%97%E6%B3%95)（DFS）和[**广度优先搜索**](https://notebook.ricear.com/project-21/doc-724/#2-%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86%E7%AE%97%E6%B3%95)（BFS）解决，BFS 一般比 DFS 更为繁琐，这里为了简洁只展现 DFS 代码。
3. 这类题型需要注意以下几点：
   1. 如果是**找路径和等于给定 $target$ 的路径**的，那么**可以不用新增一个临时变量来判断当前路径和**，**只需要用给定和 $target$ 减去节点值**，**最终结束条件判断 $target == 0$ 即可**。
   2. **二叉树的问题大部分是不需要回溯的**，因为：
      1. **二叉树的递归部分**（`dfs(root -> left)`、`dfs(root -> right)`）**已经把可能的路径穷尽了**，因此**到任意节点的路径只可能有一条**，绝对**不可能出现另外的路径也到这个满足条件的叶节点的**。
      2. **而对比二维数组**（例如[岛屿问题](https://notebook.ricear.com/project-21/doc-751)）**的 DFS**，`for`**循环向四个方向查找每次只能朝向一个方向**，并**没有穷尽路径**，因此**某一个满足条件的点可能是多条路径到该点的**，并且 `visited`**数组标记已经走过的路径是会受到另外路径是否访问的影响**，这时候**必须回溯**。
   3. **至于找到路径后是否需要 `return`**，这**取决于是否要求找到叶节点满足条件的路径**：
      1. 如果**必须找到叶节点**，那么**就要 `return`**。
      2. 如果是**到任意节点都可以**，那么必**不能 `return`**，因为**这条路径下面还可能有更深的路径满足条件**，**还要在此基础上继续递归**。
   4. **至于是否需要双重递归**（即调用根节点的 `dfs` 函数后，继续调用根左右节点的 `pathsum` 函数），**需要看题目是要求从根节点开始**，**还是从任意节点开始**。

#### 解题模板

##### 一般路径

```java
/**
 * 自顶向下（版本 1：一般路径）
 * @param root
 * @param path
 */
public void dfsFromTopToBottomV1(TreeNode root, List<Integer> path) {
    //  根节点为空直接返回
    if (root == null) {return;}

//  做出选择（将节点的值添加到路径中）
    List<Integer> pathTemp = new ArrayList<>(path);
    pathTemp.add(root.val);

//  叶节点（左子树和右子树均为空），将路径添加到结果中，然后返回
    if (root.left == null && root.right == null) {
        res.add(path);
        return;
    }

//  遍历左子树
    dfsFromTopToBottomV1(root.left, pathTemp);
    //  遍历右子树
    dfsFromTopToBottomV1(root.right, pathTemp);
}
```

##### 给定和的路径

```java
/**
 * 自顶向下（版本 2：给定和的路径）
 * @param root
 * @param path
 */
public void dfsFromTopToBottomV2(TreeNode root, int sum, List<Integer> path) {
    //  根节点为空直接返回
    if (root == null) {return;}

//  做出选择（将 sum 值减去当前节点的值，然后将当前节点的值添加到路径中）
    sum -= root.val;
    List<Integer> pathTemp = new ArrayList<>(path);
    pathTemp.add(root.val);

//  叶节点（左子树和右子树均为空），且满足给定的路径和，将路径添加到结果中，然后返回
    if (root.left == null && root.right == null && sum == 0) {
        res.add(path);
        return;
    }

//  遍历左子树
    dfsFromTopToBottomV1(root.left, pathTemp);
    //  遍历右子树
    dfsFromTopToBottomV1(root.right, pathTemp);
}
```

### 非自顶向下

#### 概述

1. 非自顶向下就是**从任意节点到任意节点的路径**，**不需要自顶向下**。
2. 这类题目的一般解题思路如下：
   
   1. **设计一个辅助函数 `maxPath()`**，**调用自身求出以一个节点为根节点的左侧最长路径 $left$ 和右侧最长路径 $right$**，**那么经过该节点的最长路径就是 $left + right$**。
   2. **接着只需要从根节点开始 DFS**，**不断更新比较全局变量即可**。
3. 这类题型 DFS 需要注意的地方：
   
   1. **$left$ 和 $right$ 代表的含义要根据题目所求设置**，比如最长路径、最大路径和等等。
   2. **全局变量 $res$ 的初值是 0 还是 `INT_MIN` 要看题目节点是否存在负值**，**如果存在就用 `INT_MIN`**，**否则就是 0**。

#### 解题模板

```java
Integer resInt = 0;
public int maxPath(TreeNode root) { /*以 root 为路径起始点的最长路径*/
    if (root == null) {return 0;}

int left = maxPath(root.left);
    int right = maxPath(root.right);
    resInt = Math.max(resInt, left + right + root.val); /*更新全局变量*/
    return Math.max(left, right) + root.val;   /*返回左右路径较长者*/
}
```

## 题目分析

### 自顶向下

#### 一般路径

##### [二叉树的所有路径](https://leetcode-cn.com/problems/binary-tree-paths)

###### 问题分析

1. 该题目属于[自顶向下](#1-1-自顶向下)类型中的[一般路径](#1-1-2-1-一般路径)，直接套用[相应模板](#1-1-2-1-一般路径)即可。
2. 该题目有两点需要注意的地方：
   1. 在 `dfs()` 方法中**新建一个变量存储当前路径的值**，**防止对原来路径的值造成影响**。
   2. **添加前缀时在遍历左子树和右子树前面添加**，**这样可以把前缀的处理变得更为简单**。

###### 参考代码

```java
//  路径列表
List<String> path = new ArrayList();

/**
 * 257. 二叉树的所有路径
 * @param root  根节点
 * @return  二叉树的所有路径
 */
public List<String> binaryTreePaths(TreeNode root) {
    dfs(root, "");
    return path;
}

/**
 * 深度优先遍历查找当前节点到叶子节点的所有路径
 * @param root  当前节点
 * @param subPath   当前节点到叶子节点的路径
 */
public void dfs(TreeNode root, String subPath) {
    //  base case
    if (root == null) {return;}

//  新建一个变量存储 subPath 的值，防止对原来 subPath 的值造成影响
    StringBuffer subPathBuffer = new StringBuffer(subPath);
    subPathBuffer.append(root.val);

if (root.left == null && root.right == null) {
        //  遍历到了叶子节点，将当前节点到叶子节点的路径添加到结果路径列表中
        path.add(subPathBuffer.toString());
        return;
    }

//  添加前缀
    subPathBuffer.append("->");
    //  遍历左子树
    dfs(root.left, subPathBuffer.toString());
    //  遍历右子树
    dfs(root.right, subPathBuffer.toString());
}
```

##### [从叶结点开始的最小字符串](https://leetcode-cn.com/problems/smallest-string-starting-from-leaf)

###### 问题分析

1. 该题目属于[自顶向下](#1-1-自顶向下)类型中的[一般路径](#1-1-2-1-一般路径)，直接套用[相应模板](#1-1-2-1-一般路径)即可。

###### 参考代码

```java
//  最小字符串
String res = "";

/**
 * 988. 从叶结点开始的最小字符串
 * @param root  根节点
 * @return  从叶结点开始的最小字符串
 */
public String smallestFromLeaf(TreeNode root) {
    dfs(root, "");
    return res;
}

/**
 * 深度优先遍历查找从叶结点开始的最小字符串
 * @param root  当前节点
 * @param path  从叶节点到当前节点的最小字符串
 */
public void dfs(TreeNode root, String path) {
    if (root == null) {return;}

StringBuffer newPath = new StringBuffer(path);
    newPath.append(String.valueOf((char)(root.val - 0 + 'a')));

if (root.left == null && root.right == null) {
        String pathReverseStr = newPath.reverse().toString();
        if (res == "") {
            res = pathReverseStr;
        } else {
            res = (res.compareTo(pathReverseStr) <= 0 ? res : pathReverseStr);
        }
        return;
    }

dfs(root.left, newPath.toString());
    dfs(root.right, newPath.toString());
}
```

#### 给定路径和的路径

##### 2.1.2.1 [路径总和 II](https://leetcode-cn.com/problems/path-sum-ii/)

###### 问题分析

1. 该题目属于[自顶向下](#1-1-自顶向下)类型中的[给定路径和的路径](#1-1-2-2-给定和的路径)，直接套用[相应模板](#1-1-2-2-给定和的路径)即可。

###### 参考代码

```java
//  路径列表
List<List<Integer>> res = new ArrayList<>();

/**
 * 113. 路径总和 II
 * @param root  根节点
 * @param targetSum 目标路径和
 * @return  所有从根节点到叶子节点路径总和等于给定目标和的路径
 */
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    List<Integer> path = new ArrayList<>();
    dfs(root, targetSum, path);
    return res;
}

/**
 * 深度优先遍历查找所有从根节点到叶子节点路径总和等于给定目标和的路径
 * @param root
 * @param targetSum
 * @param path
 */
public void dfs(TreeNode root, int targetSum, List<Integer> path) {
    if (root == null) {return;}

targetSum -= root.val;
    List<Integer> pathTemp = new ArrayList<>(path);
    pathTemp.add(root.val);

if (root.left == null && root.right == null && targetSum == 0) {
        res.add(pathTemp);
        return;
    }

dfs(root.left, targetSum, pathTemp);
    dfs(root.right, targetSum, pathTemp);
}
```

##### [路径总和 III](https://leetcode-cn.com/problems/path-sum-iii/)

###### 问题分析

1. 该题目属于[自顶向下](#1-1-自顶向下)类型中的[给定路径和的路径](#1-1-2-2-给定和的路径)，可以**采用双重递归来实现**：
   1. **先调用 `dfs()` 函数从 `root` 开始查找路径和等于给定值的路径**。
   2. **然后再调用 `pathSum()` 函数从 `root` 左右子树开始查找**。
2. 需要注意的是：
   1. 在 `dfs()` 函数中**当 $sum = 0$ 时不要直接 $return$**，**因为题目中不要求到叶子节点结束**，**所以一条路径下面可能还有另外一条**。

###### 参考代码

```java
//  路径数目
int count = 0;

/**
 * 437. 路径总和 III
 * @param root  根节点
 * @param targetSum 目标值
 * @return  二叉树里节点值之和等于 targetSum 的 路径 的数目
 */
public int pathSum(TreeNode root, int targetSum) {
    if (root == null) {return 0;}
    //  查找以当前节点为起点，路径和等于给定值的路径
    dfs(root, targetSum);
    //  查找当前节点的左子树节点值之和等于 targetSum 的路径的数目
    pathSum(root.left, targetSum);
    //  查找当前节点的右子树节点值之和等于 targetSum 的路径的数目
    pathSum(root.right, targetSum);
    return count;
}

/**
 * 深度优先遍历查找所有从根节点到叶子节点路径总和等于给定目标和的路径
 * @param root
 * @param targetSum
 */
public void dfs(TreeNode root, int targetSum) {
    if (root == null) {return;}
    targetSum -= root.val;
    if (targetSum == 0) {count++;}
    dfs(root.left, targetSum);
    dfs(root.right, targetSum);
}
```

### 非自顶向下

#### [二叉树中的最大路径和](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum)

##### 问题分析

1. 该题目属于[非自顶向下](#1-2-非自顶向下)类型，直接套用[相应模板](#1-2-2-解题模板)即可。
2. 需要注意的是：
   1. **最大路径和小于 0**，意味着**该路径和对总路径和做负贡献**，因此**不要计入到总路径中**，**将他设置为 0**。

##### 参考代码

```java
//  二叉树中的最大路径和
int res = Integer.MIN_VALUE;

/**
 * 124. 二叉树中的最大路径和
 * @param root  根节点
 * @return  二叉树中的最大路径和
 */
public int maxPathSum(TreeNode root) {
    dfs(root);
    return res;
}

/**
 * 当前节点的最大贡献值
 * @param root  当前节点
 * @return  当前节点的最大贡献值
 */
public int dfs(TreeNode root) {
    //  base case
    if (root == null) {return 0;}

//  计算左右子树的最大贡献值
    //  只有最大贡献值大于 0 时，才会选择对应子节点
    int leftGain = Math.max(dfs(root.left), 0);
    int rightGain = Math.max(dfs(root.right), 0);

//  当前节点的路径和，当其比已有最大路径和大时更新最大路径和为当前节点的路径和
    //  当前节点的路径和 = 当前节点的值 + 左子树的最大贡献值 + 右子树的最大贡献值
    res = Math.max(res, root.val + leftGain + rightGain);

//  返回当前节点的最大贡献值
    //  当前节点的最大贡献值 = 当前节点值 + 左右子树中最大的最大贡献值
    return Math.max(leftGain, rightGain) + root.val;
}
```

##### 扩展题目

###### 输出最大路径和对应的路径

1. 构建一个新的结构 `Pair` 用于存储 **经过每个节点的最大路径和** 及其 **对应的路径**。

~~~java
   public class Pair {
       int pathNum = 0;  // 存储经过当前节点的最大路径和
       List<Integer> path = new ArrayList<>();  // 存储经过当前节点的最大路径和对应的路径
       public Pair() {}
       public Pair(int _pathNum, List<Integer> _path) {
           if (_pathNum < 0) {  // 只有最大贡献值大于 0 时，才会选择对应子节点
               _pathNum = 0;
               _path = new ArrayList<>();
           }
           pathNum = _pathNum;
           path = _path;
       }
   }
   ~~~

2. 剩下的逻辑和不需要输出路径的逻辑一样，只不过在更新最大路径和的同时也要更新对应的路径。

~~~java
public class Pair {
    int pathNum = 0;  // 存储经过当前节点的最大路径和
    List<Integer> path = new ArrayList<>();  // 存储经过当前节点的最大路径和对应的路径
    public Pair() {}
    public Pair(int _pathNum, List<Integer> _path) {
        if (_pathNum < 0) {  // 只有最大贡献值大于 0 时，才会选择对应子节点
            _pathNum = 0;
            _path = new ArrayList<>();
        }
        pathNum = _pathNum;
        path = _path;
    }
}

/**
 * 124. 二叉树中的最大路径和
 * @param root  二叉树的根节点
 */
public int maxPathSum(TreeNode root) {
    dfs(root);
    for (int i = 0; i < resPath.size(); i++) {  // 输出最大路径和对应的路径
        System.out.print(resPath.get(i) + " ");
    }
    System.out.println();
    return res;
}

int res = Integer.MIN_VALUE;  // 存储最终最大路径和
List<Integer> resPath = new ArrayList<>();  // 存储最终最大路径和对应的路径
public Pair dfs(TreeNode root) {
    if (root == null) {return new Pair();}

Pair leftPair = dfs(root.left);  // 计算左子树的最大贡献值
    Pair rightPair = dfs(root.right);  // 计算右子树的最大贡献值
    
    if (leftPair.pathNum + rightPair.pathNum + root.val > res) {  // 更新最终最大路径和及其对应的路径
        List<Integer> temp = new ArrayList<>();
        temp.addAll(leftPair.path);
        temp.add(root.val);
        temp.addAll(rightPair.path);
        res = leftPair.pathNum + rightPair.pathNum + root.val;
        resPath = temp;
    }
    
    int tmpRes = 0;  // 当前节点的最大路径和
    List<Integer> tmpResPath = new ArrayList<>();  // 当前节点的最大路径和对应的路径
    if (leftPair.pathNum > rightPair.pathNum) {  // 更新当前节点的最大路径和机器对应的路径
        tmpRes = leftPair.pathNum;
        tmpResPath.addAll(leftPair.path);
    } else if (rightPair.pathNum > leftPair.pathNum) {
        tmpRes = rightPair.pathNum;
        tmpResPath.addAll(rightPair.path);
    }
    tmpRes += root.val;
    tmpResPath.add(root.val);
    
    return new Pair(tmpRes, tmpResPath);
}
~~~

#### [最长同值路径](https://leetcode-cn.com/problems/longest-univalue-path/)

##### 问题分析

1. 该题目属于[非自顶向下](#1-2-非自顶向下)类型，直接套用[相应模板](#1-2-2-解题模板)即可。
2. 需要注意的是：
   1. **对当前节点的值和其左右子节点的值的对比应该放在递归遍历完左右子树后进行**。

##### 参考代码

```java
//  同值路径的最大长度
int res = 0;

/**
 * 687. 最长同值路径
 * @param root  根节点
 * @return  同值路径的最大长度
 */
public int longestUnivaluePath(TreeNode root) {
    dfs(root);
    return res;
}

/**
 * 深度优先遍历求同值路径的最大长度
 * @param root  当前节点
 * @return  同值路径的最大长度
 */
public int dfs(TreeNode root) {
    if (root == null) {return 0;}

int left = dfs(root.left);
    int right = dfs(root.right);

//  如果存在左子节点，并且当前节点的值和左子节点的值相同，则更新左最长路径，否则，令左最长路径为 0
    if (root.left != null && root.val == root.left.val) {
        left++;
    } else {
        left = 0;
    }
    //  如果存在右子节点，并且当前节点的值和右子节点的值相同，则更新右最长路径，否则，令右最长路径为 0
    if (root.right != null && root.val == root.right.val) {
        right++;
    } else {
        right = 0;
    }

res = Math.max(res, left + right);
    return Math.max(left, right);
}
```

#### [二叉树的直径](https://leetcode-cn.com/problems/diameter-of-binary-tree/)

##### 问题分析

1. 该题目属于[非自顶向下](#1-2-非自顶向下)类型，直接套用[相应模板](#1-2-2-解题模板)即可。

##### 参考代码

```java
//  二叉树的直径
int res = 0;

/**
 * 543. 二叉树的直径
 * @param root  根节点
 * @return  二叉树的直径
 */
public int diameterOfBinaryTree(TreeNode root) {
    dfs(root);
    return res;
}

/**
 * 深度优先遍历求二叉树的直径
 * @param root  当前节点
 * @return  二叉树的直径
 */
public int dfs(TreeNode root) {
    if (root == null) {return 0;}

int left = dfs(root.left);
    int right = dfs(root.right);

res = Math.max(res, left + right);

return Math.max(left, right) + 1;
}
```

## 参考文献

1. [一篇文章解决所有二叉树路径问题（问题分析 + 分类模板 + 题目剖析）](https://leetcode-cn.com/problems/path-sum-ii/solution/yi-pian-wen-zhang-jie-jue-suo-you-er-cha-oo63)。
2. [CodeTop036 二叉树中的最大路径和](https://blog.csdn.net/Oblak_ZY/article/details/123340357)。