剑指Offer-24.二叉树中和为某一值的路径(C++/Java)

题目：

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)

分析：

LeetCode上有一道相同的题目，以前记录过：LeetCode 113. Path Sum II路径总和 II (C++)，就不再讲解了。

程序：

C++

class Solution {

public:

    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {

        vector<int> v;

        dfs(root, v, expectNumber);

        return res;

    }

    void dfs(TreeNode* root, vector<int> &v, int sum){

        if(root == nullptr)

            return;

        v.push_back(root->val);

        if(root->left == nullptr && root->right == nullptr){

            if(sum == root->val)

                res.push_back(v);

        }

        else{

            dfs(root->left, v, sum-root->val);

            dfs(root->right, v, sum-root->val);

        }

        v.pop_back();

    }

private:

    vector<vector<int>> res;

};

Java

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) {

        res = new ArrayList<>();

        ArrayList<Integer> l = new ArrayList<>();

        dfs(root, l, target);

        return res;

    }

    public void dfs(TreeNode root, ArrayList<Integer> l, int sum){

        if(root == null)

            return;

        l.add(root.val);

        if(root.left == null && root.right == null){

            if(root.val == sum){

                res.add(new ArrayList(l));

            }

        }

        else{

            dfs(root.left, l, sum-root.val);

            dfs(root.right, l, sum-root.val);

        }

        l.remove(l.size()-1);

    }

    private ArrayList<ArrayList<Integer>> res;

}

巴特西

剑指Offer-24.二叉树中和为某一值的路径(C++/Java)

题目：

分析：

程序：

最新文章

热门文章