34.二叉树中和为某一值的路径(二).md

34. 二叉树中何为某一值得路径

题目描述

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

• 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
• 2.叶子节点是指没有子节点的节点
• 3.路径只能从父节点到子节点，不能从子节点到父节点
• 4.总节点数目为 n

思路 & 解答

主要是借助队列，将遍历的节点放进队列中，到叶子节点之后计算和，然后再回溯到上面一层的时候，将队列最后一个元素取出来，放进当前的元素。

代码如下：

import java.util.ArrayList;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.stream.Collectors;
/**
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>> results = new ArrayList<>();
        LinkedList<Integer> queue = new LinkedList<>();
        int sum = 0;
        if (root != null) {
            addDatas(root, target, results, queue, sum);
        }
        return results;
    }

    public void addDatas(TreeNode root, int target, ArrayList<ArrayList<Integer>> results, LinkedList<Integer> queue, Integer sum) {
        if (root != null) {
            sum = sum + root.val;
            queue.add(root.val);
            if (sum == target && root.left == null && root.right == null) {
                addResult(results, queue);
            } else {
                addDatas(root.left, target, results, queue, sum);
                addDatas(root.right, target, results, queue, sum);
            }
            queue.pollLast();
            sum = sum - root.val;
        }
    }

    public void addResult(ArrayList<ArrayList<Integer>> results, Queue<Integer> queue) {
        ArrayList<Integer> result = (ArrayList<Integer>) queue.stream().collect(Collectors.toList());
        results.add(result);
    }
}

C++ 代码实现如下：

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    int sum = 0;
    vector<vector<int>> results;

    vector<vector<int>> FindPath(TreeNode *root, int expectNumber) {
        deque<int> queue;
        if (root != NULL) {
            addDatas(root, expectNumber, queue);
        }
        return results;
    }

    void addDatas(TreeNode *root, int target, deque<int> queue) {
        if (root != NULL) {
            sum = sum + root->val;
            queue.push_back(root->val);
            if (sum == target && root->left == NULL && root->right == NULL) {
                addResult(queue);
            } else {
                addDatas(root->left, target, queue);
                addDatas(root->right, target, queue);
            }
            queue.pop_back();
            sum = sum - root->val;
        }
    }

    void addResult(deque<int> queue) {
        vector<int> result = vector<int>();
        while (!queue.empty()) {
            result.push_back(queue.front());
            queue.pop_front();
        }
        results.push_back(result);
    }
};

时间复杂度：O(n)，n 为二叉树的节点个数，遍历完所有的节点 空间复杂度：O(n)，借助了额外的空间