【剑指Offer】【树】二叉树中和为某一值的路径

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

A：选择前序遍历，因为前序遍历先访问根节点

　选择从后向前递归，每次减去当前节点的值，直到遍历到叶子节点，若值减为0则找到了一条路径和，填入listAll中

　　若当前不是叶子节点且剩余的值还未为零，则递归调用该节点的左子树，再递归调用该节点的右子树

　　若不符合，则删除结点

/*

struct TreeNode {

	int val;

	struct TreeNode *left;

	struct TreeNode *right;

	TreeNode(int x) :

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

	}

};*/

class Solution {

private:

    vector<vector<int> > listAll;

    vector<int> list;

    void ifFind(TreeNode * node , int left)

    {

        //存入路径list

        list.push_back(node->val);

        //是否是叶子节点，且路径和一致

        if((left - node->val == 0) && (node->left == nullptr) && (node->right == nullptr))

        {

            listAll.push_back(list); //{10,5,7} ==> {10,12}

        }

        else

        {

            if(node->left)

            {

                ifFind(node->left, left - node->val);

            }

            if(node->right)

            {

                ifFind(node->right, left - node->val);

            }

        }

        list.pop_back(); //{10,5,4} => ture => true

    }

public:

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

    {

        //{10,5,4,7,12}

        if(root != nullptr)

        {

            ifFind(root,expectNumber);

        }

        return listAll;

    }

};

巴特西

【剑指Offer】【树】二叉树中和为某一值的路径

最新文章

热门文章