剑指offer之面试题24：二叉树中和为某一值的路径

题目：

成都地区优秀IDC服务器托管提供商(创新互联).为客户提供专业的联通服务器托管,四川各地服务器托管,联通服务器托管、多线服务器托管.托管咨询专线：13518219792

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

例如输入下图中二叉树和整数22，则打印出两条路径，第一条路径包含结点10、12，第二条路径包含结点10、5和7。

思路：

1、判断根结点是否为空

2、单一路径要有vector path保存；

3、多条路径要有vector> ret保存并返回；

4、从根结点分析，由于每次遍历都要先把结点的值进行访问所以是前序遍历；

5、在遍历的同时，需要保存访问过结点的值，并且和expectNumber相减得到剩余expectNumber

6、只有根结点才用判断最后的值和剩余expectnumber相等，不相等，pop出path

7、根结点相等即为递归退出条件

代码：

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    vector > FindPath(TreeNode* root,int expectNumber) 
    {
		vector> ret;
        vector path;
        if(root==NULL)
        {
            return ret;
        }
        findLeaf(ret,path,root,expectNumber);
        return ret;
    }
    void findLeaf(vector> &ret,vector &path,TreeNode *node,int left)
    {
        path.push_back(node->val);
        //终止条件
        if(left-node->val==0&&node->left==NULL&&node->right==NULL)
        {
            ret.push_back(path);
        }
        else
        {
            if(node->left)
            {
                int l=left-node->val;
                findLeaf(ret,path,node->left,l);
            }
            if(node->right)
            {
                int l=left-node->val;
                findLeaf(ret,path,node->right,l);
            }
        }
        //是叶子节点但是路径和不一样，pop这个叶子节点
        path.pop_back();
    }
};

精简版代码：

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
    vector >allRes;
    vector tmp;
    void dfsFind(TreeNode * node , int left){
        tmp.push_back(node->val);
        if(left-node->val == 0 && !node->left && !node->right)
            allRes.push_back(tmp);
        else {
            if(node->left) dfsFind(node->left, left-node->val);
            if(node->right) dfsFind(node->right, left-node->val);
        }
        tmp.pop_back(); 
    }
public:
    vector > FindPath(TreeNode* root,int expectNumber) {
        if(root) dfsFind(root, expectNumber);
        return allRes;
    }
};

网页名称：剑指offer之面试题24：二叉树中和为某一值的路径
本文地址：http://jkwzsj.com/article/ieeeco.html