剑指Offer Java版 面试题34：二叉树中和为某一值的路径

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

练习地址

https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca

参考答案

import java.util.ArrayList;
/**
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>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        find(root, target, 0, new ArrayList<Integer>(), result);
        return result;
    }
    
    private void find(TreeNode node, int target, int sum, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> result) {
        sum += node.val;
        path.add(node.val);
        // 如果是叶节点，并且路径上节点值的和等于输入的值，则打印出这条路径
        if (node.left == null && node.right == null) {
            if (sum == target) {
                ArrayList<Integer> list = new ArrayList<>();
                for (Integer val : path) {
                    list.add(val);
                }
                result.add(list);
            }
        } else {
            // 如果不是叶节点，则遍历它的子节点
            if (node.left != null) {
                find(node.left, target, sum, path, result);
            }
            if (node.right != null) {
                find(node.right, target, sum, path, result);
            }
        }
        // 在返回父节点之前，在路径上删除当前节点
        path.remove(path.size() - 1);
    }
}

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(logn)。

👉剑指Offer Java版目录
👉剑指Offer Java版专题