面试题34:二叉树中和为某一值的路径

题目:输入一颗二叉树和一个整数,打印出二叉树中节点值的和为输入整数的所有路径。从输的根节点开始往下一直到叶子节点所经过的节点形成一条路径。
思路:新建两个数组listAll和list,list用来存储路径,如果list里面的路径满足要求,则添加到listAll里面。
解决方案:

public class Question34 {
    static class BinaryTreeNode {
        int value;
        BinaryTreeNode left;
        BinaryTreeNode right;

        public BinaryTreeNode(int value) {
            this.value = value;
        }
    }
    private static ArrayList<ArrayList<Integer>> listAll = new ArrayList<ArrayList<Integer>>();
    private static ArrayList<Integer> list = new ArrayList<Integer>();
    public static ArrayList<ArrayList<Integer>> findPath(BinaryTreeNode root, int target){
        if (root == null) return null;
        list.add(root.value);
        target -= root.value;
        if (target == 0 && root.left == null && root.right == null){
            listAll.add(new ArrayList<Integer>(list));
        }
        findPath(root.left, target);
        findPath(root.right, target);
        list.remove(list.size() - 1);
        return listAll;
    }

    public static void main(String[] args) {
        BinaryTreeNode pHead = new BinaryTreeNode(1);
        BinaryTreeNode pAhead = new BinaryTreeNode(3);
        BinaryTreeNode pBhead = new BinaryTreeNode(5);
        BinaryTreeNode pChead = new BinaryTreeNode(7);
        BinaryTreeNode pDhead = new BinaryTreeNode(9);
        pHead.left = pAhead;
        pHead.right = pBhead;
        pBhead.left = pChead;
        pAhead.left = pDhead;
        System.out.println(findPath(pHead, 13));
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容