二叉树的路径处理问题
路径处理问题，实质上是使用树的遍历方法对树进行遍历，常常采用树的先序遍历方法对树进行遍历，对树的先序遍历方法稍加改动，改动先序遍历时对中间节点的处理逻辑和对左右子树的处理逻辑来实现题目的要求。
- 处理从根节点到每一个叶子节点的路径（即该二叉树的所有路径）上的所有节点，
例如leetcode257，问题描述及代码如下：
问题描述：
给定一个二叉树，返回所有从根节点到叶子节点的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
解决思路：从根节点开始进行中序遍历，先处理中序遍历时当前节点，将其入字符串，字符串中保存着当前路径中到目前为止的所有节点，然后处理左右子树，在处理左右子树时要判断是否已经为叶子节点，如果已经到达叶子节点，则将当前字符串入线性表，否则分别判断左右子树是否为空，递归处理其中不为空的子树。
代码如下：字符串用于保存当前路径，即从根节点开始到当前路径的目前节点的所有节点，线性表用于存储所有的路径，每一条路径在线性表中为一个字符串，String对象.trim() 返回当前字符串的去除头尾空白后的副本。
class Solution {
//先序遍历树，先处理当前节点，然后遍历左右子树，依次处理，加入list中
//而且左右子树需要分开加入
public List<String> binaryTreePaths(TreeNode root) {
List<String> list = new ArrayList<>();
String s = "";
paths(root, list, s);
return list;
}
private void paths(TreeNode root, List<String> list, String s){
//到达叶节点时停止递归
if(root == null){
return;
}
//先序遍历，处理中间节点
//要判断是否已经到达一条路径的尽头，并在到达时将字符串入线性表
//实质上还是对先序遍历的稍加改动
s += root.val + " ";
if(root.left == null && root.right == null){
list.add(s.trim().replace(" ", "->"));
}
//先序遍历，处理左右子树
//处理逻辑为，左右子树中任何一个不为空，便递归处理该子树
if(root.left != null){
paths(root.left, list, s);
}
if(root.right != null){
paths(root.right, list, s);
}
}
} 2.leetcode 112路径总和
问题描述：
给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。
解决思路：写一个方法，该方法通过先序遍历统计根节点到叶子节点的每一条路径上节点和值等于目的值的数量，注意是从根节点开始，到叶子节点结束的所有路径。
代码：
class Solution {
//根节点到叶子节点
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null){
return false;
}
return (path(root, sum)>0) ? true : false;
}
private int path(TreeNode root, int sum){
//递归终止条件
if(root == null){
return 0;
}
//先序遍历，先处理中间节点
//关于result在这里声明的问题，需要说明一下，多多体会递归时在递归方法中声明的变量所起到的所用
//result在递归方法中声明，然后每次递归调用方法处理左右子树返回的值都给result，方法最后返回result
//每次声明的result都只在当前递归调用层有效，但由于将递归调用的方法返回值付给了当前层的reuslt
//这就使得最外层的result得到了层层往里的递归调用的方法的返回值
//也可以反过来考虑，从叶子节点开始看，或者从找到的那个和为目的和的路径的终节点看，该终结点返回result为1
//上一层的result会加上该终结点统计得到的1
//层层上传，使得最终的result是1
int result = 0;
if(root.left == null && root.right == null && sum == root.val){
result ++;
}
//先序遍历，后递归处理左右子树
//注意，此处将题目要求的求和变成，每次判断当前节点值是否等于目的和值的减去前面所有节点和和值
//将求和变成减法
//sum - root.val
if(root.left != null){
result += path(root.left, sum-root.val);
}
if(root.right != null){
result +=path(root.right, sum-root.val);
}
return result;
}
} 3.leetcode 437路径总和lll
问题描述：
给定一个二叉树，它的每个结点都存放着一个整数值。
找出路径和等于给定数值的路径总数。
路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
示例：
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1
返回 3。和等于 8 的路径有:
1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11 解决思路：因为不要求起始节点为根节点，因此需要遍历每一个节点，从每一个节点开始计算当前节点下的所有路径值和是否为目的值，由于树的递归操作的遍历行，遍历每一个节点时，可以采用递归，先处理中间节点，然后递归处理左右子树。需要写一个方法，该方法接受一个节点、目的和值作为参数，返回该节点作为起始位置下和值为目的和值的路径数。
代码：
class Solution {
//统计从每一个节点开始的所有路径求和是否等于目的值
//考虑到树的特殊性，在遍历统计每一个节点时，不需要使用for循环，考虑树的递归遍历，只需要每次处理中间节点
//并递归调用处理其左右子树
public int pathSum(TreeNode root, int sum) {
//防止root.left或者root.right出现NullPointerException，需要判断当前节点是否为空
if(root == null){
return 0;
}
return path(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}
//path先序遍历
//path方法传入当前节点及目的和值，判断从当前节点开始有多少条路径的和值等于目的值sum
private int path(TreeNode root, int sum){
//递归至叶节点返回条件
if(root == null){
return 0;
}
//先序遍历，先处理当前节点
int result = 0;
if(root.val == sum){
result++;
}
//先序遍历，处理完当前节点后，处理左右子树
result += path(root.left, sum - root.val);
result += path(root.right, sum - root.val);
return result;
}
} 4.leetcode687题
问题描述：
给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。
注意：两个节点之间的路径长度由它们之间的边数表示。
示例 1:
输入:
5
/ \
4 5
/ \ \
1 1 5
输出:
2
示例 2:
输入:
1
/ \
4 5
/ \ \
4 4 5
输出:
2
注意: 给定的二叉树不超过10000个结点。 树的高度不超过1000。
解决思路：
思路一，先序遍历，最容易想到的就是先序遍历，或许是先序遍历用习惯了？先写一个方法，该方法接受一个节点作为参数，并计算出以该参数节点作为根节点的树下，经过根节点的最长同值路径，三种情况，左右子树加根节点组成最长同值路径，左子树加根节点组成最长同值路径，右子树加根节点组成最长同值路径；然后再另外一个方法中遍历这棵树，在访问每一个节点时，调用上述方法，并传入当前节点作为参数，计算当前节点下且经过当前节点的最长同值路径，保存遍历过程中得到的最长同值路径。写出了上述思路的实现过程，但总是有测试用例出错误，排查了一上午也没解决，上述思路的逻辑判断过多，出错误后难以排查解决。
实际上，在做这道题时，产生上述思路的原因是习惯于使用先序遍历，当先序遍历不好解决问题的时候，应当考虑中序遍历，和后序遍历，一定要多思考先序、中序、后序遍历的区别，及三种遍历各自的遍历路径和处理顺序。
思路二，后序遍历，先处理左右子树，然后处理中间节点，在处理中间节点的时候，判断左右子树的值是否与中间节点的值相同，若相同，则同值路径加长，不相同，则说明左右子树的同值路径无法与中间节点合并加长，故清零；由于是后序遍历，因此处理顺序是从最底层开始向上层层处理。这个思路的处理方式是从下往上找同值路径，并判断左右子树能否与当前连接成更大的同值路径，已经连接好的下层同值路径长度保存在result中，在和中间节点连接新的同值路径时，左右子树的同值路径必须是单向路径（即左右子树中的同值路径不会是左中右这么连接的），因此find返回值为left与right中较大的，即左右子树中同值路径较长的。
class Solution {
public int longestUnivaluePath(TreeNode root) {
find(root);
return result;
}
int result = 0;
private int find(TreeNode root){
if(root == null)
return 0;
int left = find(root.left);
int right = find(root.right);
if(root.left != null && root.val == root.left.val)
left++;
else
left = 0;
if(root.right != null && root.val == root.right.val)
right++;
else
right = 0;
result = Math.max(result, left+right);
return Math.max(left, right);
}
}
投递SHEIN等公司7个岗位 >