剑指offer（24）——C++实现输出二叉树为某一值的所有路径

一时失言乱红尘 2024-04-18 10:42 17阅读 0赞

# 题目 #

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

# 解题思路 #

从根节点开始，每遍历一个值就将其装入数组path中，当其到达叶节点并且和等于sum了就将路径压入reslut后，清空path，进行递归其左右节点。

# 完整代码 #

/*24-二叉树中和为某一值的路径*/
    #include<iostream>
    #include<vector>
    using namespace std;
    struct TreeNode {
        
    	int val;
    	struct TreeNode *left;
    	struct TreeNode *right;
    	TreeNode(int x) :
    			val(x), left(NULL), right(NULL) {
        
    	}
    };
    class Solution {
        
    public:
    	vector<vector<int>> result;
    	vector<int> path;
    	//
    	void findsum(TreeNode* root, int sum)
    	{
        
    		if (root == NULL) return;
    		path.push_back(root->val);
    		
    		if (!root->left && !root->right&& sum == root->val)//到达叶节点并且得到sum则将该路径压入result 
    			result.push_back(path);
    		else//递归
    		{
        
    			if (root->left)
    				findsum(root->left, sum - root->val);
    			if (root->right)
    				findsum(root->right, sum - root->val);
    		}
    		path.pop_back();
    	}
    	
    	vector<vector<int> > FindPath(TreeNode* root, int expectNumber) {
        	
    		findsum(root, expectNumber);
    		return result;
    	}
    };
    
    int main()
    {
        
    	TreeNode *root = new TreeNode(10); TreeNode *p1 = new TreeNode(5); TreeNode *p2 = new TreeNode(12);
    	TreeNode *p3 = new TreeNode(4); TreeNode *p4 = new TreeNode(7); 
    	root->left = p1; root->right = p2; p1->left = p3; p1->right = p4; 
    	Solution s;
    	vector<vector<int>> result;
    	result = s.FindPath(root, 22);
    	int row = result.size();
    	int crow = result[0].size();
    	for (int i = 0; i < row; ++i)
    	{
        
    		for (int j = 0; j < crow; ++j)
    			cout << result[i][j]<<' ';
    	}
    	cout << endl;
    	return 0;
    }