朕苦二叉树久矣，故需模板来镇住此妖孽，不求时间复杂度最好，只求能够AC

二叉树分类

二叉树路径问题可以分为两类

1. 自顶向下：

从某一个节点（不一定是根节点），从上往下寻找路径，到某一个节点（不一定是叶子节点）结束。

2. 非自顶向下：

就是从任意节点到任意节点的路径，不需要自顶向下

解题模板

自顶向下

这里只给出深度优先的模板dfs

一般路径

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

void dfs(TreeNode root) {
	if (root == null) return;
	path.add(root.val); // 添加本层节点数值
	
	if (root.left == null && root.right == null) { // 到达叶子节点
		result.add(new ArrayList(path); // 满足要求，加入结果集中
	}
	
	if (root.left != null) {
		dfs(root.left);
		path.removeLast(); //移除递归结束前添加的的节点
	}

	if (root.right!= null) {
		dfs(root.right);
		path.removeLast(); //移除递归结束前添加的的节点
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

给定和的路径

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

void dfs(TreeNode root, int target) {
	if (root == null) return;
	path.add(root.val); // 添加本层节点数值
	target -= root.val; //减去本层的节点数值
	
	if (root.left == null && root.right == null && target== 0) { // 到达叶子节点并且路径上的值符合要求
		result.add(new ArrayList(path); // 满足要求，加入结果集中
	}
	
	if (root.left != null) {
		dfs(root.left);
		path.removeLast(); //移除递归结束前添加的的节点
	}

	if (root.right!= null) {
		dfs(root.right);
		path.removeLast(); //移除递归结束前添加的的节点
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

注意点：

1. 如果是找路径和等于给定target的路径的，那么可以不用新增一个临时变量cursum来判断当前路径和，只需要用给定和target减去节点值，最终结束条件判断target==0即可
2. 是否要回溯：二叉树的问题大部分是不需要回溯的，原因如下：

• 二叉树的递归部分：dfs(root->left),dfs(root->right)已经把可能的路径穷尽了,因此到任意叶节点的路径只可能有一条，绝对不可能出现另外的路径也到这个满足条件的叶节点的;
• 而对比二维数组(例如迷宫问题)的DFS,for循环向四个方向查找每次只能朝向一个方向，并没有穷尽路径，因此某一个满足条件的点可能是有多条路径到该点的

3. 找到路径后是否要return:
   取决于题目是否要求找到叶节点满足条件的路径,如果必须到叶节点,那么就要return;
   但如果是到任意节点都可以，那么必不能return,因为这条路径下面还可能有更深的路径满足条件，还要在此基础上继续递归
4. 取决于题目是否要求找到叶节点满足条件的路径,如果必须到叶节点,那么就要return;
   但如果是到任意节点都可以，那么必不能return,因为这条路径下面还可能有更深的路径满足条件，还要在此基础上继续递归
   看题目要不要求从根节点开始的，还是从任意节点开始

非自顶向下

设计一个辅助函数maxpath，调用自身求出以一个节点为根节点的左侧最长路径left和右侧最长路径right，那么经过该节点的最长路径就是left+right
接着只需要从根节点开始dfs,不断比较更新全局变量即可

int result = 0;
public int maxPath(TreeNode root) {
	if (root == null) return 0;
	// 后序遍历，得出左孩子和右孩子的最长路径
	int left = maxPath(root.left);
	int right = maxPath(root.right);
	result = Math.max(result, left + right + root.val); // 当前路径和左孩子最长路径-> 根 -> 右孩子最长路径之和比较
	return Math.max(left, right); //返回左右路径最长者
}
1
2
3
4
5
6
7
8
9

注意：

1. left,right代表的含义要根据题目所求设置，比如最长路径、最大路径和等等
2. 全局变量res的初值设置是0还是INT_MIN要看题目节点是否存在负值,如果存在就用INT_MIN，否则就是0
3. 注意两点之间路径为1，因此一个点是不能构成路径的

具体题目

自定向下

257. 二叉树的所有路径
接套用模板1即可，注意把"->"放在递归调用中

	public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        dfs(root, res, "");
        return res;
    }

    public void dfs(TreeNode node, List<String> res, String path) {
        if (node == null) return;

        if (node.left == null && node.right == null) {
            path += node.val;
            res.add(path);
            return;
        }

        dfs(node.left, res, path + node.val + "->");
        dfs(node.right, res, path + node.val + "->");
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

113. 路径总和 II
直接套用模板2

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

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

    public void getPath(TreeNode node, int targetSum) {
        if (node == null) return;
        list.add(node.val);
        targetSum -= node.val;

        if (node.left == null && node.right == null && targetSum == 0) {
            result.add(new ArrayList(list));
        }

        if (node.left != null) {
            getPath(node.left, targetSum);
            list.remove(list.size() - 1);
        }
        if (node.right != null) {
            getPath(node.right, targetSum);
            list.remove(list.size() - 1);
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

437. 路径总和 III
双重递归：先调用dfs函数从root开始查找路径，再调用pathsum函数到root左右子树开始查找
套用模板2

	int result = 0;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        getPath(root, targetSum); // 从根节点开始遍历
        pathSum(root.left, targetSum); // 以左孩子为根节点开始遍历
        pathSum(root.right, targetSum); // 以右孩子为根节点开始遍历
        return result;
    }

    public void getPath(TreeNode node, long targetSum) {
        if (node == null) return;

        targetSum -= node.val;
        if (targetSum == 0) {
            result++;
        }

        getPath(node.left, targetSum);
        getPath(node.right, targetSum);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

988. 从叶结点开始的最小字符串
套用模板1

	StringBuilder builder = new StringBuilder();
    String min = null;
    public String smallestFromLeaf(TreeNode root) {
        if (root == null) return min;
        dfs(root);
        return min;
    }

    public void dfs(TreeNode node) {
        if (node == null) return;
        char tmp = (char) (node.val + 'a');
        builder.append(tmp);
        if (node.left == null && node.right == null) {
            String str = builder.reverse().toString();
            builder.reverse();
            //System.out.println(str);
            if (min == null || min.compareTo(str) > 0) {
                min = str;
            }
            return;
        }

        if (node.left != null) {
            dfs(node.left);
            builder.deleteCharAt(builder.length() - 1);
        }

        if (node.right != null) {
            dfs(node.right);
            builder.deleteCharAt(builder.length() - 1);
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

非自顶向下

124. 二叉树中的最大路径和
left,right分别为根节点左右子树最大路径和。

注意：如果最大路径和<0,意味着该路径和对总路径和做负贡献，因此不要计入到总路径中，将它设置为0

	private int maxSum = Integer.MIN_VALUE; //注意节点值可能为负数，因此要设置为最小值

    public int maxPathSum(TreeNode root) {
        intMaxPath(root); 以root为路径起始点的最长路径
        return maxSum;
    }


    public int intMaxPath(TreeNode node) { 
        if (node == null) return 0;
        int left = Math.max(0, intMaxPath(node.left));
        int right = Math.max(0, intMaxPath(node.right));

        maxSum = Math.max(maxSum, left + right + node.val);//比较当前最大路径和与左右子树最长路径加上根节点值的较大值，更新全局变量
        return Math.max(left + node.val, right + node.val);  //返回左右子树较长的路径加上根节点值
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

687. 最长同值路径

	int ans = Integer.MIN_VALUE;
    public int longestUnivaluePath(TreeNode root) {
        if (root == null) return 0;
        getPath(root);
        return ans;
    }

    public int getPath(TreeNode node) {
        if (node == null) return 0;
        int left = getPath(node.left);
        int right = getPath(node.right);

		// 如果存在左子节点和根节点同值，更新左最长路径;否则左最长路径为0
        if (node.left != null && node.val != node.left.val) {
            left = 0;
        }

        if (node.right != null && node.val != node.right.val) {
            right = 0;
        }

        ans = Math.max(ans, left + right);
        return Math.max(left, right) + 1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

543. 二叉树的直径

	int ans = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        maxPath(root);
        return ans;
    }

    public int maxPath(TreeNode node) {
        if (node == null) return 0;
        int left = maxPath(node.left);
        int right = maxPath(node.right);
        
        ans = Math.max(ans, left + right);
        return Math.max(left, right) + 1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14