二叉树中和为某一值的路径

题目描述

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

分析

递归,分别在左右子树里找符合 target = target - root.val 的路径。

代码:

import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
ArrayList<ArrayList<Integer>> pathList = new ArrayList<ArrayList<Integer>>();
if (root == null || root.val > target) return pathList;
ArrayList<Integer> path = new ArrayList<Integer>();
FindPath(root, target, pathList, path);
return pathList;
}
public void FindPath(TreeNode root, int target, ArrayList<ArrayList<Integer>> pathList, ArrayList<Integer> path) {
if (root == null || root.val > target) {
path.clear();
} else if (root.val == target) {
if (root.left == null && root.right == null) {
path.add(root.val);
pathList.add(path);
}
else path.clear();
} else {
path.add(root.val);
target -= root.val;
ArrayList<Integer> path2 = new ArrayList<Integer>();
path2.addAll(path);
FindPath(root.left, target, pathList, path);
FindPath(root.right, target, pathList, path2);
}
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD's Blog All Rights Reserved.

访客数 : | 访问量 :