【剑指Offer】024——二叉树中和为某一值的路径（树）

题目描述

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

解题思路

用前序遍历（根->左->右）的方式访问到某一结点时，把该结点添加到路径上，并用目标值减去该节点的值。如果该结点为叶结点并且目标值减去该节点的值刚好为0，则当前的路径符合要求，我们把加入res数组中。如果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回到它的父结点。因此我们在函数退出之前要在路径上删除当前结点，以确保返回父结点时路径刚好是从根结点到父结点的路径。

参考代码

import java.util.ArrayList;
class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}

public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> temp = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
        // 没找到情况
        if (root == null)
            return res;
        target -= root.val;
        temp.add(root.val);
        if (target == 0 && root.left == null && root.right == null) {
            res.add(new ArrayList<Integer>(temp));
        } else {
            FindPath(root.left, target);
            FindPath(root.right, target);
        }
        temp.remove(temp.size() - 1);  // 为了能够回到上一个结点
        // 之所以不用加上root.val的值，在上一层递归中，上一个target的值没有减去当前值
        return res;
    }
}

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def FindPath(self, root, expectNumber):
        # write code here
        if not root:
            return []
        temp = []
        if not root.left and not root.right and expectNumber == root.val:
            return [[root.val]]
        else:
            left = self.FindPath(root.left, expectNumber - root.val)
            right = self.FindPath(root.right, expectNumber- root.val)
            for item in left + right:
                temp.append([root.val] + item)
        return temp

个人订阅号

image