二叉树中和为某一值的路径牛客网程序员面试金典 C++ Python

二叉树中和为某一值的路径牛客网程序员面试金典

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

c++

/*

struct TreeNode {

	int val;

	struct TreeNode *left;

	struct TreeNode *right;

	TreeNode(int x) :

			val(x), left(NULL), right(NULL) {

	}

};*/

class Solution {

public:

    //run:3ms memory:484k

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

        vector<vector<int>> ret;

        vector<int> lt;

        if (NULL == root) return ret;

        return FindAPath(root,expectNumber,ret,lt);

    }

    vector<vector<int>> FindAPath(TreeNode* root, int expectNumber,

                                  vector<vector<int>> &path_list,vector<int> lt){

        if (NULL == root) return path_list;

        expectNumber -= root->val;

        lt.push_back(root->val);

        if (expectNumber != 0){

            FindAPath(root->left,expectNumber,path_list,lt);

            FindAPath(root->right,expectNumber,path_list,lt);

        }else if(NULL == root->left && NULL == root->right)

            path_list.push_back(lt);

        return path_list;

    }

    //run:3ms memory:480k

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

        if(root) dfsFind(root, expectNumber);

        return allRes;

    }

    void dfsFind(TreeNode * node , int target){

        tmp.push_back(node->val);

        if(!node->left && !node->right){

            if(target - node->val == 0) allRes.push_back(tmp);

        }else{

            if(node->left) dfsFind(node->left, target - node->val);

            if(node->right) dfsFind(node->right, target - node->val);

        }

        if(!tmp.empty())

            tmp.pop_back();

    }

    private:

        vector<vector<int> >allRes;

        vector<int> tmp;

};

Python

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    # run:32ms memory:5736k

    def FindPath(self, root, expectNumber):

        if None == root: return []

        return self.FindAPath(root,expectNumber,[],[])

    def FindAPath(self,root,expectNumber,path_list,lt):

        if None == root: return

        expectNumber = expectNumber - root.val

        lt.append(root.val)

        if expectNumber !=0:

            left_lt = list(lt)

            self.FindAPath(root.left,expectNumber,path_list,left_lt)

            right_lt = list(lt)

            self.FindAPath(root.right,expectNumber,path_list,right_lt)

        elif root.left == None and root.right == None:

            path_list.append(lt)

        return path_list

巴特西

二叉树中和为某一值的路径牛客网程序员面试金典 C++ Python

最新文章

热门文章

巴特西

二叉树中和为某一值的路径 牛客网 程序员面试金典 C++ Python

最新文章

热门文章

二叉树中和为某一值的路径牛客网程序员面试金典 C++ Python