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

题目描述

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

题目分析

深度优先搜索即可。

C++

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Solution
{
public:
    vector<vector<int> > FindPath(TreeNode *root, int expectNumber)
    {
        vector<vector<int> > ans;
        if (!root)
            return ans;
        FindPath2(root, expectNumber, vector<int>(), ans);
        return ans;
    }

    void FindPath2(TreeNode *root, int expectNumber, vector<int> v, vector<vector<int> > &ans)
    {
        v.push_back(root->val);
        if (!root->left && !root->right)
        {
            if (root->val == expectNumber)
                ans.push_back(v);
        }
        else
        {
            vector<int> ans1, ans2;
            if (root->left)
                FindPath2(root->left, expectNumber - root->val, v, ans);

            if (root->right)
                FindPath2(root->right, expectNumber - root->val, v, ans);
        }
    }
};

Java

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<>();
        if (root == null)
            return ans;
        FindPath2(root, target, new ArrayList<>(), ans);
        return ans;
    }

    private void FindPath2(TreeNode root, int target, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> ans) {
        list.add(root.val);
        if (root.left == null && root.right == null && root.val == target) {
            ans.add(list);
        } else {
            if (root.left != null)
                FindPath2(root.left, target - root.val, new ArrayList<>(list), ans);
            if (root.right != null)
                FindPath2(root.right, target - root.val, new ArrayList<>(list), ans);
        }
    }
}