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

 

题目描述

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

示例二叉树

target为5的话, 上面二叉树的结果就是[[1,4],[1,2,2]]

代码

import java.util.ArrayList;
import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
        if(root == null) return ans;
        Stack<Integer> stack = new Stack<Integer>();
        func(ans, stack, root, 0, target);
        return ans;
    }

    private void func(ArrayList<ArrayList<Integer>> ans, Stack<Integer> stack, TreeNode root, int sum, int target){
        sum += root.val;
        stack.push(root.val);
        if(root.left == null && root.right == null){
            if(sum == target){
                ans.add(new ArrayList<Integer>(stack));
            }
        }

        if(root.left != null){
            func(ans, stack, root.left, sum, target);
        }

        if(root.right != null){
            func(ans, stack, root.right, sum, target);
        }
        stack.pop();
    }
}

思路

树的题目, 很容易想到用递归做, 这道题也是如此. 并且利用栈进行回溯.

递归的终点是该节点为叶子节点的时候. 判断sum是否等于target, 将符合的结果填入ans.

利用stack来存储走过的路径, 回溯时候弹出.

扩展

如果题目中给的二叉树中, 值全是正整数, 那么, 可以在递归的过程中进行剪枝, 提升效率.