二叉树节点为某一值的路径

题目描述
输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,数组长度大的数组靠前)

思路:要寻找到所有路径,可以使用DFS,要保证最后的和一定就行。保证按数组大小排序,可以使用优先队列来实现。

public class Solution { 
   //根据列表长度排序

     ArrayList<ArrayList<Integer>> pathList= new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) { 
        if (root == null) return pathList;
        DFS(root, target);
        //调整数组顺序
        pathList.sort((o1,o2)->o2.size()-o1.size());        //函数式编程
        return pathList;
    }
    public void DFS(TreeNode root, int target) { 
        path.add(root.val);
        target-=root.val;
        if (root.left == null&&root.right==null&&target==0) { 
                pathList.add(new ArrayList<Integer>(path));      
        }
        //递归
       if(root.left!=null) DFS(root.left, target); //左子树
        if(root.right!=null)DFS(root.right, target); //右子树
        //回退到父节点
        path.remove(path.size() - 1);
    }
}
    原文作者:北风扬尘尘飞扬
    原文地址: https://blog.csdn.net/weixin_45458665/article/details/102943102
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞