首页 > 其他 > 详细

剑指offer二十四之二叉树中和为某一值的路径

时间:2017-10-06 23:41:33      阅读:402      评论:0      收藏:0      [点我收藏+]

一、题目

  输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

二、思路

     详见代码

三、代码

1、解答代码

技术分享
import java.util.ArrayList;

public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        ArrayList<ArrayList<Integer>> paths = new ArrayList<ArrayList<Integer>>();
        if (root == null) return paths;
        find(paths, new ArrayList<Integer>(), root, target);
        return paths;
    }

    public void find(ArrayList<ArrayList<Integer>> paths, ArrayList<Integer> path, TreeNode root, int target) {
        path.add(root.val);
        if (root.left == null && root.right == null) {
            if (target == root.val) {
                paths.add(path);
            }
            return;
        }

        //存储右节点的路径
        ArrayList<Integer> path2 = new ArrayList<>();
        path2.addAll(path);

        if (root.left != null) find(paths, path, root.left, target - root.val);
        if (root.right != null) find(paths, path2, root.right, target - root.val);
    }
}
View Code

2、节点类

技术分享
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
View Code

3、测试代码

技术分享
import java.util.ArrayList;

public class TestMain {
    public static void main(String[] args) {
        //建立二叉树,注意必须逆序建立,先建立子节点,再逆序往上建立,因为非叶子结点会使用到下面的节点,而初始化是按顺序初始化的,不逆序建立会报错
        TreeNode G = new TreeNode(3, null, null);
        TreeNode F = new TreeNode(6, null, null);
        TreeNode E = new TreeNode(5, null, null);
        TreeNode D = new TreeNode(4, null, null);
        TreeNode C = new TreeNode(3, F, G);
        TreeNode B = new TreeNode(2, D, E);
        TreeNode A = new TreeNode(1, B, C);

        //调用方法
        Solution solution = new Solution();
        ArrayList<ArrayList<Integer>> paths = solution.FindPath(A,7);

        /*输出所有路径  
            1 2 4
            1 3 3   
        */
        for (ArrayList<Integer> s : paths) {
            for (int i = 0; i < s.size(); i++) {
                System.out.print(s.get(i) + " ");
            }
            System.out.println();   
        }
    }
}
View Code

-----------------------------------------------------------------------

参考链接:https://www.nowcoder.com/questionTerminal/b736e784e3e34731af99065031301bca

剑指offer二十四之二叉树中和为某一值的路径

原文:http://www.cnblogs.com/hezhiyao/p/7633208.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!