1. 路径相关的题目

257. 二叉树的所有路径 - E (opens new window)

所有从根节点到叶子节点的路径

113. 路径总和 II - M (opens new window)

求满足条件的所有路径(从根节点到叶子节点)

112. 路径总和 - E (opens new window)

从根节点到叶子节点 路径总和等于给定目标和的路径。

988. 从叶结点开始的最小字符串 - M (opens new window)

求所有路径中的最小字符串(从叶子节点开始)

129. 求根节点到叶节点数字之和 - M (opens new window)

437. 路径总和 III - M (opens new window)

路径: 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

2. 解题思路

关于二叉树路径的题目，首先要明确一点:

是否是从(根节点->叶子节点 || 叶子节点->根节点)

2.1 根节点-->叶子节点

2.1.1 二叉树的所有路径(根->叶子)

257. 二叉树的所有路径 - E (opens new window)

这道题是用String来表示路径的。(为了效率可以采用StringBuilder)

    public class Solution{

        List<String> result = new ArrayList();

        public List<String> binaryTreePaths(TreeNode root) {

            dfs(root,new StringBuilder());

            return result;
        }
        // 根->叶。 DFS完美
        public void dfs(TreeNode root, StringBuilder path){
            if(root == null){
                return ;
            }

            path.append(root.val);
            if(root.left == null && root.right == null){
                result.add(path.toString());
            }
            
            path.append("->");
            // 有些同学，可能出于优化代码的角度，想把new StringBuilde(path)也提取出来，这个不可以的，
            dfs(root.left, new StringBuilder(path));

            dfs(root.right,new StringBuilder(path));
        }

    }

---

113. 路径总和 II - M (opens new window)

求满足条件的所有路径(从根节点到叶子节点)

这道题和257 (opens new window) 基本一样，区别在于用List来代表路径。解法自然是一样。

public class Solution{
    
    List<List<Integer>> result = new ArrayList();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        
        dfs(root,new ArrayList(),targetSum);
        
        return result;
    }

    public void dfs(TreeNode root,List<Integer> path,int targetSum){
        if(root == null){
            return;
        }
        path.add(root.val);
        targetSum -= root.val;

        if(root.left == null && root.right == null && targetSum == 0){
            result.add(path);
        }

        // 这里我们发现遍历左右子树，都得重新构建路径，还能优化。
        dfs(root.left, new ArrayList(path),targetSum);

        dfs(root.right,new ArrayList(path),targetSum);
    }

}

上面的解法遍历左右子树都得重新构建路径，这里进行优化一下：

只在添加的时候构建路径。

具体做法如下:

public class Solution{

    List<List<Integer>> result = new ArrayList();

    List<Integer> path = new ArrayList();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root,targetSum);
        return result;
    }

    public dfs(TreeNode root, int targetSum){
        if(root == null) return ;

        targetSum -= root.val;
        path.add(root.val);

        if(root.left == null && root.right == null && targetSum == 0){
            result.add(new Array(path));
        }

        dfs(root.left,targetSum);
        dfs(root.right,targetSum);
        // 这个地方很容易忽略, 向上回溯
        path.remove(path.size()-1);

    }
}

---

112. 路径总和 - E (opens new window)

从根节点到叶子节点 路径总和等于给定目标和的路径。

跟上面的题目一样，都是采用DFS来解题。

public class Solution{

    boolean result = false;

    public boolean hasPathSum(TreeNode root,int targetSum){
        dfs(root,targetSum);

        return result;
    }

    public dfs(TreeNode root, int targetSum){
        if(root == null) return;

        targetSum -= root.val;

        if(root.left == null && root.right == null && targetSum == 0){
            result = true;
        }

        dfs(root.left,targetSum);

        dfs(root.right,targetSum);
    }

}

优化代码：

public class Solution{

    public boolean hasPathSum(TreeNode root,int targetSum){
        if(root == null){
            return false;
        }

        targetSum -= root.val;
        
        // 叶子节点
        if(root.left == null && root.right == null){
            return (targetSum == 0);
        }

        return hasPathSum(root.left,targetSum) || hasPathSum(root.right, target);
    }

}

---

988. 从叶结点开始的最小字符串 - M (opens new window)

求所有路径中的最小字符串(从叶子节点开始)

对于不熟练的同学，有一个小技巧：从叶子节点开始 <==> 从根节点开始，采用头插法。

这道题只要掌握小技巧，那就跟上面的题是一个套路。无非需要排个序而已

public class Solution{
    List<String> paths = new ArrayList();

    public String smallestFromLeaf(TreeNode root) {
        dfs(root,new StringBuilder());
        if(paths.isEmpty()) return "";
        
        // 进行排序
        Collections.sort(paths);

        return paths.get(0);
    }

    public dfs(TreeNode root,StringBuilder path){
        
        if(root == null) return;
        // 头插法
        path.insert(0,(char)('a'+root.val));

        if(root.left == null && root.right == null){
            paths.add(path.toString());
        }

        dfs(root.left , new StringBuilder(path));

        dfs(root.right, new StringBuilder(path));

    }

}

优化一下(忽略不计)

public class Solution{

    List<String> paths = new ArrayList();

    StringBuilder sb = new StringBuilder();

     public String smallestFromLeaf(TreeNode root) {
        dfs(root);

        if(paths.isEmpty()) return "";

        Collections.sort(paths);

        return paths.get(0);
     }

     public dfs(TreeNode root){
         if(root == null) return ;

         sb.insert(0,(char)('a'+root.val));

         if(root.left == null && root.right == null){
             paths.add(new String(sb));
         }

         dfs(root.left);
         dfs(root.right);
         // 回溯 （注意这里StringBuilder的删除API:deleteCharAt(int index)）
         sb.deleteCharAt(0);
     }

}

---

129. 求根节点到叶节点数字之和 - M (opens new window)

此题依然是：

根节点 -> 叶子节点

这里我们先用获取所有路径的方法来做：

借助于 Integer.valueOf(String s) 来转换数字。

public class Solution{

    List<String> paths = new ArrayList();

    StringBuilder path = new StringBuilder();

    public int sumNumbers(TreeNode root) {
        dfs(root);

        // 获取到所有路径之后，开始求和
        int sum = 0;

        for(int i = 0; i < paths.size(); i++){
            sum += Integer.valueOf(paths.get(i));
        }

        return sum;
    }

    public void dfs(TreeNode root){
        if(root == null){
            return;
        }

        path.append(root.val);

        if(root.left == null && root.right == null){
            paths.add(new String(path));
        }

        dfs(root.left);

        dfs(root.right);

        path.deleteCharAt(path.length()-1);
    }
}

上面利用Integer来转换数字可能通用性不是很好，下面我们来转换成求和来做:

sum * 10 + root.val;

public class Solution{
    int sum = 0;

    public int sumNumbers(TreeNode root) {
        dfs(root,0);

        return sum;
    }

    public void dfs(TreeNode root,int tmpSum){
        
        if(root == null) return ;

        tmpSum = 10 * tmpSum + root.val;

        // 到达叶子节点，就求和
        if(root.left == null && root.right == null){
            sum += tmpSum;
        }

        dfs(root.left,tmpSum);

        dfs(root.right,tmpSum);
    }

}

这里还有更好的DFS:

public class Solution{
   public int sumNumbers(TreeNode root) {

        return dfs(root, 0);
    }
    public int dfs(TreeNode root, int preSum){
        if(root == null )return 0;

        preSum = preSum * 10 + root.val;

        if (root.left == null && root.right == null){
            return preSum;
        }
        return dfs(root.left, preSum)+dfs(root.right, preSum);
    }

递归不要太深究细节。(结束条件、核心逻辑想清楚即可)

---

437. 路径总和 III - M (opens new window)

微软 - 5, 字节 - 3

这个题目比较特殊：路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）

class Solution {

    int paths = 0;

    public int pathSum(TreeNode root, int targetSum) {

        // 从根节点开始
        dfs(root,targetSum);
        // 从左节点开始
        pathSum(root.left,targetSum);
        // 从右节点开始
        pathSum(root.right,targetSum);

        return paths;
    }

    public void dfs(TreeNode root,int sum){
        
        if(root == null) return ;

        sum -= root.val;

        if(sum == 0){
            paths += 1;
        }

        dfs(root.left, sum);

        dfs(root.right, sum);

    }
}

---

124. 二叉树中的最大路径和 - H (opens new window)

==高频题==

字节 - 11 , 微软 - 5

public class Solution{
    
    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        if(root == null) {
            return 0;
        }

        int left = Math.max(0,maxPathSum(root.left));

        int right = Math.max(0,maxPathSum(root.right));

        max = Math.max(max,left+right+root.val);

        return Math.max(left,right) + root.val;

    }
}