一道编程题——二叉树路径和为指定值

题目描述

给定一个二叉树和一个值 sum，请找出所有的根节点到叶子节点的节点值之和等于 sum 的路径。返回一个二维数组，数组中保存路径上节点的值。

返回结果：[[5,4,11,2], [5,8,9]]

题目分析

本题涉及二叉树的遍历，需要注意的是题目中所需要的路径为根节点到叶子节点，所以即使路径和已经为 sum ，也是不符合题目要求的路径。

二叉树的遍历既可以使用 DFS 也可以用 BFS 。DFS 的话需要使用递归，终止递归的条件为节点不存在，在递归的过程中，如果遇到节点为叶子节点并且路径和为所给定的值，则将这个路径保存下来，所以我们需要两个数组，一个数组用来暂存每一个遍历的路径，另外一个用来保存满足条件的路径。

代码实现

python实现

DFS/递归

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import copy
class Solution:
    def __init__(self):
        self.re = []
        
    def pathSum(self , root , sum ):
        # write code here
        tmp = []
        self.findPath(root, sum, tmp)
        return self.re
    # python函数传参形参为数组时传的是引用
    def findPath(self, root, sum, tmp):
        # 递归终止条件：节点为空
        if(not root):return None
        # 节点存在则加入到路径中
        tmp.append(root.val)
        if(not root.left and not root.right and sum==root.val):
            # 这里需要用到深拷贝，否则tmp数组被加入到re中之后，仍然会被改变
            self.re.append(copy.deepcopy(tmp))
        # 递归左右子树
        self.findPath(root.left, sum-root.val, tmp)
        self.findPath(root.right, sum-root.val, tmp)
        # 出递归，删去末尾节点，以便递归另外一个方向
        tmp.pop()

BFS

# BFS
class Solution2:
    def pathSum(self , root , ssum ):
        # write code here
        if(not root):return None
        # path数组保存根节点到当前节点的路径值
        path = [root.val]
        tmp = [[root, path]]
        re = []
        while tmp:
            node, path = tmp.pop(0)
            if not node.left and not node.right and sum(path) == ssum:
                re.append(path)
            if node.left:
                tmp.append([node.left, path+[node.left.val]])
            if node.right:
                tmp.append([node.right, path+[node.right.val]])
        return re

C++实现

DFS/递归

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > pathSum(TreeNode* root, int sum) {
        // write code here
        vector<vector<int>> result;
        vector<int> tmp;
        findPath(root,sum, result, tmp);
        return result;
    }
    
    void findPath(TreeNode* root, int sum, vector<vector<int>> &re, vector<int> tmp){
        if(root == NULL)return ;
        tmp.push_back(root->val);
        if(root->left == NULL && root->right ==NULL && sum == root->val){
            re.push_back(tmp);
        }
        findPath(root->left, sum-root->val, re, tmp);
        findPath(root->right, sum-root->val, re, tmp);
        //tmp.pop_back(); // tmp数组传引用的话需要pop_back()
    }
};