Question

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


关键词：二叉树 求和 BFS

Solution

DFS

时间复杂度：O(log(N))

空间复杂度：O(N/2·log(N))

• Python

class Solution:
    # 返回二维列表，内部每个列表表示找到的路径
    def __init__(self):
        self.ans = []
        
    def FindPath(self, root, expectNumber):
        if root:
            self.dfs(root, expectNumber, [])
        return self.ans
    
    def dfs(self, node, num, path):
        if not node.left and not node.right and node.val == num:
            self.ans.append(path + [node.val])
        if node.left:
            self.dfs(node.left, num - node.val, path + [node.val])
        if node.right:
            self.dfs(node.right, num - node.val, path + [node.val])

• C++

class Solution {
public:
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
        vector<vector<int>> ans;
        vector<int> temp;
        if(root)
            dfs(root, expectNumber, temp, ans);
        return ans;
    }
    void dfs(TreeNode* node, int num, vector<int> &path, vector<vector<int>> &ans){
        path.push_back(node->val);
        if((node->left == NULL) && (node->right == NULL) && (node->val == num)){
            //path.push_back(node->val);
            ans.push_back(path);
        }
        if(node->left)
            dfs(node->left, num - node->val, path, ans);
        if(node->right)
            dfs(node->right, num - node->val, path, ans);
        path.pop_back();
    }
};