在二叉树中找出和为某一值的所有路径-白红宇

在二叉树中找出和为某一值的所有路径

阅读量：2349 次

发布时间：2019-05-10

本文共 1038 字，大约阅读时间需要 3 分钟。

题目：输入一个整数和一棵二元树。

从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。

打印出和与输入整数相等的所有路径。

例如输入整数22 和如下二元树

/ \

5 12

/ \

4 7

则打印出两条路径：10, 12 和10, 5, 7。

二元树节点的数据结构定义为：

struct BinaryTreeNode // a node in the binary tree

{

int value; // value of node

BinaryTreeNode *left; // left child of node

BinaryTreeNode *right; // right child of node

};

思路：递归遍历的同时回溯，用一个数组存放路径

import java.util.ArrayList;/**public class TreeNode {    int val = 0;    TreeNode left = null;    TreeNode right = null;    public TreeNode(int val) {        this.val = val;    }}*/public class Solution {    private ArrayList
    
     
      > listAll = new ArrayList
      
       
        >();    private ArrayList
        
          list = new ArrayList
         
          (); public ArrayList
          
           
            > FindPath(TreeNode root,int target) { if(root == null) return listAll; list.add(root.val); target -= root.val; if(target == 0 && root.left == null && root.right == null) listAll.add(new ArrayList
            
             (list)); FindPath(root.left, target); FindPath(root.right, target); list.remove(list.size()-1); return listAll; }}