二叉树路径问题

• 二叉树所有路径
• • 分析
  • JAVA实现
  • 力扣提交
• 找到一个和为sum的到达叶子节点的路径
• • 分析
  • JAVA实现
  • 力扣提交
• 求路径（中间一段）
• • C++实现
• 打印根节点到任意节点的路径
• • JAVA实现

二叉树所有路径

257二叉树所有路径

分析

前序遍历二叉树+递归实现回溯
深度优先搜索dfs

JAVA实现

//静态内部类//二叉树节点public static class TreeNode{int data;bTree257.TreeNode leftChild;bTree257.TreeNode rightChild;public TreeNode(int data) {this.data = data;}}

二叉树的构建

/*** 前序遍历的链表节点的顺序.来创建二叉树* @param inputList* @return*/public static bTree257.TreeNode precreatBinaryTree(LinkedList inputList){bTree257.TreeNode node = null;if(inputList==null||inputList.isEmpty()){return null;}Integer data = inputList.removeFirst();if(data!=null){//根左右。。。。node = new bTree257.TreeNode(data);node.leftChild=precreatBinaryTree(inputList);node.rightChild = precreatBinaryTree(inputList);}//将根节点返回（用于遍历，不返回根节点，这个树怎么找。。。。。）return node;}

前序遍历代码（写着玩玩）

    /*** 前序遍历* @param node*/public static void preOrderTraveral(bTree257.TreeNode node){if(node==null){return;}System.out.println(node.data);preOrderTraveral(node.leftChild);preOrderTraveral(node.rightChild);}

遍历所有路径:

    public static void dfs(TreeNode root,String path,List ans){if(root!=null){StringBuffer sb = new StringBuffer(path);sb.append(root.data);if(root.leftChild==null&&root.rightChild==null){ans.add(sb.toString());return ;}else {sb.append("->");dfs(root.leftChild,sb.toString(),ans);dfs(root.rightChild,sb.toString(),ans);}return ;}}public List binaryTreePaths(TreeNode root) {List ans = new ArrayList<>();dfs(root,"",ans);return ans;}

递归出口1：if(root.leftChildnull&&root.rightChildnull)
也就是达到这个条件回溯到前面的状态。。。。。
递归出口2：return ;
也就是遍历完成了左右孩子，则回溯到上一个状态

测试方法：

    public static void main(String[] args) {//前序创建二叉树//LinkedList inputList = new LinkedList(Arrays.asList(new Integer[]{1,2,4,null,null,5,null,null,3,null,6}));//LinkedList inputList = new LinkedList(Arrays.asList(new Integer[]{8,5,1,null,null,2,null,null,7}));LinkedList inputList = new LinkedList(Arrays.asList(new Integer[]{}));
//        inputList.add(8);
//        inputList.add(5);
//        inputList.add(1);
//        inputList.add(null);
//        inputList.add(null);
//        inputList.add(2);
//        inputList.add(null);
//        inputList.add(null);
//        inputList.add(7);System.out.println("请按照前序输入二叉树节点:");Scanner in =new Scanner(System.in);int a=0;Scanner sc = new Scanner(System.in);String inputString = sc.nextLine();String stringArray[] = inputString.split(" ");int num[] = new int[stringArray.length];for (int i = 0; i < stringArray.length; i++) {if(Integer.parseInt(stringArray[i])==0){inputList.add(null);}else {inputList.add(Integer.parseInt(stringArray[i]));}}System.out.println("二叉树构建成功！");bTree257.TreeNode treeNode = precreatBinaryTree(inputList);System.out.println("前序遍历如下：");preOrderTraveral(treeNode);System.out.println("遍历所有路径");//1 2 4 0 0 5 0 0 3 0 6//ans存储所有的路径List ans = new ArrayList<>();dfs(treeNode,"",ans);for (int i =0;iSystem.out.println(ans.get(i));}}

前序遍历如下：

力扣提交

力扣提交代码：

class Solution {public static void dfs(TreeNode root,String path,List ans){if(root!=null){StringBuffer sb = new StringBuffer(path);sb.append(root.val);if(root.left==null&&root.right==null){ans.add(sb.toString());return ;}else {sb.append("->");dfs(root.left,sb.toString(),ans);dfs(root.right,sb.toString(),ans);}return ;}}public List binaryTreePaths(TreeNode root) {List ans = new ArrayList<>();dfs(root,"",ans);return ans;}
}

找到一个和为sum的到达叶子节点的路径

路径总和

分析

就是在之前的二叉树路径问题上加一点求和代码就行。
将最后的结果（字符串数组，一维度）转为二维数组，遍历求和每一行的值，看其是否等于待求的数。

	    int length = 0;for (int i =0;i//System.out.println(ans.get(i));String str = ans.get(i);String[] strs=str.split("->");System.out.println(Arrays.toString(strs));length = Math.max(length,strs.length);}System.out.println(length);int result[][] = new int[ans.size()][length];for (int i =0;i//System.out.println(ans.get(i));String str = ans.get(i);String[] strs=str.split("->");for (int j =0;jresult[i][j]= Integer.parseInt(strs[j]);}}int total = 8;int sum = 0;for (int i =0;ifor (int  j=0;jsum += result[i][j];}if(sum==total){System.out.println("找到了");}if(i==ans.size()-1&&sum!=total){System.out.println("没找到");}sum=0;}

JAVA实现

package algorithmProblem;import java.util.*;public class bTree112 {//静态内部类//二叉树节点public static class TreeNode{int data;bTree112.TreeNode leftChild;bTree112.TreeNode rightChild;public TreeNode(int data) {this.data = data;}}/*** 前序遍历的链表节点的顺序.来创建二叉树* @param inputList* @return*/public static bTree112.TreeNode precreatBinaryTree(LinkedList inputList){bTree112.TreeNode node = null;if(inputList==null||inputList.isEmpty()){return null;}Integer data = inputList.removeFirst();if(data!=null){//根左右。。。。node = new bTree112.TreeNode(data);node.leftChild=precreatBinaryTree(inputList);node.rightChild = precreatBinaryTree(inputList);}//将根节点返回（用于遍历，不返回根节点，这个树怎么找。。。。。）return node;}/*** 前序遍历* @param node*/public static void preOrderTraveral(bTree112.TreeNode node){if(node==null){return;}System.out.println(node.data);preOrderTraveral(node.leftChild);preOrderTraveral(node.rightChild);}public static void dfs(bTree112.TreeNode root, String path, List ans){if(root!=null){StringBuffer sb = new StringBuffer(path);sb.append(root.data);if(root.leftChild==null&&root.rightChild==null){ans.add(sb.toString());return ;}else {sb.append("->");dfs(root.leftChild,sb.toString(),ans);dfs(root.rightChild,sb.toString(),ans);}return ;}}public ArrayList> binaryTreePaths(bTree112.TreeNode root) {List ans = new ArrayList<>();ArrayList> list = new ArrayList>();LinkedList mylist = new LinkedList();dfs(root,"",ans);return list;}public static boolean hasPathSum(TreeNode root, int targetSum) {System.out.println("遍历所有路径");//1 2 4 0 0 5 0 0 3 0 6//ans存储所有的路径List ans = new ArrayList<>();dfs(root,"",ans);int length = 0;for (int i =0;i//System.out.println(ans.get(i));String str = ans.get(i);String[] strs=str.split("->");System.out.println(Arrays.toString(strs));length = Math.max(length,strs.length);}System.out.println(length);int result[][] = new int[ans.size()][length];for (int i =0;i//System.out.println(ans.get(i));String str = ans.get(i);String[] strs=str.split("->");for (int j =0;jresult[i][j]= Integer.parseInt(strs[j]);}}int total = targetSum;int sum = 0;for (int i =0;ifor (int  j=0;jsum += result[i][j];}if(sum==total){System.out.println("找到了");return true;}if(i==ans.size()-1&&sum!=total){System.out.println("没找到");return false;}sum=0;}return false;}public static void main(String[] args) {//前序创建二叉树//LinkedList inputList = new LinkedList(Arrays.asList(new Integer[]{1,2,4,null,null,5,null,null,3,null,6}));//LinkedList inputList = new LinkedList(Arrays.asList(new Integer[]{8,5,1,null,null,2,null,null,7}));LinkedList inputList = new LinkedList(Arrays.asList(new Integer[]{}));
//        inputList.add(8);
//        inputList.add(5);
//        inputList.add(1);
//        inputList.add(null);
//        inputList.add(null);
//        inputList.add(2);
//        inputList.add(null);
//        inputList.add(null);
//        inputList.add(7);System.out.println("请按照前序输入二叉树节点:");Scanner in =new Scanner(System.in);int a=0;Scanner sc = new Scanner(System.in);String inputString = sc.nextLine();String stringArray[] = inputString.split(" ");int num[] = new int[stringArray.length];for (int i = 0; i < stringArray.length; i++) {if(Integer.parseInt(stringArray[i])==0){inputList.add(null);}else {inputList.add(Integer.parseInt(stringArray[i]));}}System.out.println("二叉树构建成功！");bTree112.TreeNode treeNode = precreatBinaryTree(inputList);System.out.println("前序遍历如下：");preOrderTraveral(treeNode);System.out.println("遍历所有路径");//1 2 4 0 0 5 0 0 3 0 6//ans存储所有的路径List ans = new ArrayList<>();dfs(treeNode,"",ans);int length = 0;for (int i =0;i//System.out.println(ans.get(i));String str = ans.get(i);String[] strs=str.split("->");System.out.println(Arrays.toString(strs));length = Math.max(length,strs.length);}System.out.println(length);int result[][] = new int[ans.size()][length];for (int i =0;i//System.out.println(ans.get(i));String str = ans.get(i);String[] strs=str.split("->");for (int j =0;jresult[i][j]= Integer.parseInt(strs[j]);}}int total = 8;int sum = 0;for (int i =0;ifor (int  j=0;jsum += result[i][j];}if(sum==total){System.out.println("找到了");}if(i==ans.size()-1&&sum!=total){System.out.println("没找到");}sum=0;}//System.out.println(hasPathSum(treeNode,8));}
}

找和为8的路径，找到了。（1，2，5）

力扣提交

力扣代码如下：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public static void dfs(TreeNode root, String path, List ans){if(root!=null){StringBuffer sb = new StringBuffer(path);sb.append(root.val);if(root.left==null&&root.right==null){ans.add(sb.toString());return ;}else {sb.append("->");dfs(root.left,sb.toString(),ans);dfs(root.right,sb.toString(),ans);}return ;}}public boolean hasPathSum(TreeNode root, int targetSum) {System.out.println("遍历所有路径");//1 2 4 0 0 5 0 0 3 0 6//ans存储所有的路径List ans = new ArrayList<>();dfs(root,"",ans);int length = 0;for (int i =0;i//System.out.println(ans.get(i));String str = ans.get(i);String[] strs=str.split("->");System.out.println(Arrays.toString(strs));length = Math.max(length,strs.length);}System.out.println(length);int result[][] = new int[ans.size()][length];for (int i =0;i//System.out.println(ans.get(i));String str = ans.get(i);String[] strs=str.split("->");for (int j =0;jresult[i][j]= Integer.parseInt(strs[j]);}}int total = targetSum;int sum = 0;for (int i =0;ifor (int  j=0;jsum += result[i][j];}if(sum==total){System.out.println("找到了");return true;}if(i==ans.size()-1&&sum!=total){System.out.println("没找到");return false;}sum=0;}return false;}
}

求路径（中间一段）

C++实现

#include 
#include 
using namespace std;
const int N = 10010;
int T[N];
int dis;
int p[N];int a[] = {0, 8, 5, 7, 1, 2};void printPath(int j){for(int i = 0; i <= j; i ++){if(p[i] == 0){continue;}printf("%d ", p[i]);}printf("\n");return;
}void findPath(int i, int j, int d, int length){if (a[i] == dis){printf("%d\n", a[i]);return;}d += a[i];p[j] = a[i];if (d == dis){printPath(j);return;}if (d < dis){if(2 * i <= length){findPath(2 * i, j + 1, d, length);}if(2 * i + 1 <= length){findPath(2 * i + 1, j + 1, d, length);}}return;}int main(){scanf("%d", &dis);int length = 5;for(int i = 1; i <= length; i ++){memset(p, 0, sizeof p);findPath(i, 0, 0, length);}system("pause");
}

打印根节点到任意节点的路径

例如1 到18路径为：1 9 14 15 17 18

JAVA实现

package algorithmProblem;import java.util.*;public class bTree112Re {//静态内部类//二叉树节点public static class TreeNode{int data;bTree112Re.TreeNode leftChild;bTree112Re.TreeNode rightChild;public TreeNode(int data) {this.data = data;}}/*** 前序遍历的链表节点的顺序.来创建二叉树* @param inputList* @return*/public static bTree112Re.TreeNode precreatBinaryTree(LinkedList inputList){bTree112Re.TreeNode node = null;if(inputList==null||inputList.isEmpty()){return null;}Integer data = inputList.removeFirst();if(data!=null){//根左右。。。。node = new bTree112Re.TreeNode(data);node.leftChild=precreatBinaryTree(inputList);node.rightChild = precreatBinaryTree(inputList);}//将根节点返回（用于遍历，不返回根节点，这个树怎么找。。。。。）return node;}/*** 前序遍历* @param node*/public static void preOrderTraveral(bTree112Re.TreeNode node){if(node==null){return;}System.out.println(node.data);preOrderTraveral(node.leftChild);preOrderTraveral(node.rightChild);}public static void dfs(bTree112Re.TreeNode root, String path, List ans){if(root!=null){StringBuffer sb = new StringBuffer(path);sb.append(root.data);if(root.leftChild==null&&root.rightChild==null){ans.add(sb.toString());return ;}else {sb.append("->");dfs(root.leftChild,sb.toString(),ans);dfs(root.rightChild,sb.toString(),ans);}return ;}}public ArrayList> binaryTreePaths(bTree112Re.TreeNode root) {List ans = new ArrayList<>();ArrayList> list = new ArrayList>();LinkedList mylist = new LinkedList();dfs(root,"",ans);return list;}/*** 打印根节点到任意节点的路径* @param root 根引用（指针）* @param rootData 根节点数据值* @param leafData 任意子节点数据值* @return*/public static LinkedList findPath(bTree112Re.TreeNode root, int rootData,int leafData) {System.out.println("遍历所有路径");//1 2 4 0 0 5 0 0 3 0 6//ans存储所有的路径List ans = new ArrayList<>();dfs(root,"",ans);int length = 0;for (int i =0;i//System.out.println(ans.get(i));String str = ans.get(i);String[] strs=str.split("->");System.out.println(Arrays.toString(strs));length = Math.max(length,strs.length);}//System.out.println(length);int result[][] = new int[ans.size()][length];for (int i =0;i//System.out.println(ans.get(i));String str = ans.get(i);String[] strs=str.split("->");for (int j =0;jresult[i][j]= Integer.parseInt(strs[j]);}}int start = rootData;int end = leafData;LinkedList resultList = new LinkedList();for (int i =0;iresultList.clear();int path = 100000;for (int  j=0;j//sum += result[i][j];if(start==result[i][j]){resultList.add(result[i][j]);path = j;}if(pathresultList.add(result[i][j]);}if(end==result[i][j]){return resultList;}}}return null;}public static void main(String[] args) {//前序创建二叉树//LinkedList inputList = new LinkedList(Arrays.asList(new Integer[]{1,2,4,null,null,5,null,null,3,null,6}));//LinkedList inputList = new LinkedList(Arrays.asList(new Integer[]{8,5,1,null,null,2,null,null,7}));LinkedList inputList = new LinkedList(Arrays.asList(new Integer[]{}));
//        inputList.add(8);
//        inputList.add(5);
//        inputList.add(1);
//        inputList.add(null);
//        inputList.add(null);
//        inputList.add(2);
//        inputList.add(null);
//        inputList.add(null);
//        inputList.add(7);System.out.println("请按照前序输入二叉树节点:");Scanner in =new Scanner(System.in);int a=0;Scanner sc = new Scanner(System.in);String inputString = sc.nextLine();String stringArray[] = inputString.split(" ");int num[] = new int[stringArray.length];for (int i = 0; i < stringArray.length; i++) {if(Integer.parseInt(stringArray[i])==0){inputList.add(null);}else {inputList.add(Integer.parseInt(stringArray[i]));}}System.out.println("二叉树构建成功！");bTree112Re.TreeNode treeNode = precreatBinaryTree(inputList);System.out.println("前序遍历如下：");preOrderTraveral(treeNode);LinkedList list = new LinkedList();Scanner sin =new Scanner(System.in);int exit=0;int rootData=0;int leafData=0;while (exit!=-1){System.out.println("请输入起始查找节点的值");rootData=sin.nextInt();//输入一个整数System.out.println("请输结束位置节点的值");leafData=sin.nextInt();//输入一个整数list = findPath(treeNode,rootData,leafData);if(list!=null){System.out.print("路径为: ");for (int i =0;iSystem.out.print(list.get(i)+" ");}}else {System.out.println("路径不存在.....请重新输入");}System.out.println("如果退出，请输入-1......");System.out.println("如果继续查找，按任意键继续.....");exit=sin.nextInt();//输入一个整数System.out.println("请继续输入节点值...");}}
}