【面试题】剑指offer25--二叉树中和为某一值的路径

拼搏现实的明天。 2022-06-13 08:26 98阅读 0赞

输入一颗二叉树和一整数，打印出二叉树中节点值的和为输入整数的所有路径。

从树的根节点开始往下一直到叶节点经过的结点形成一条路径。

例如：输入的二叉树如下图所示，输入的整数位22

![Center][]

由图可以知道，路径为22 的路径有两条。

第一条是包含节点10,12;

第二条路径包含节点10,5,7;

访问这颗二叉树的过程如下：

![Center 1][]

代码实现：

#include<iostream>
    using namespace std;
    #include<vector>
    struct BinaryTreeNode
    {
    	int _value;
    	BinaryTreeNode* _left;
    	BinaryTreeNode* _right;
    
    };
    
    void FindPath(BinaryTreeNode* root, int exp)
    {
    	if (root == NULL)
    	{
    		return;
    	}
    	std::vector<int> path;
    	int curr = 0;
    	FindPath(root, exp, path, curr);
    }
    
    void FindPath(BinaryTreeNode* root, int exp, std::vector<int>& path, int& curr)
    {
    	curr += root->_value;
    	path.push_back(root->_value);
    
    	bool isLeaf = root->_left == NULL&&root->_right == NULL;
    	if (curr == exp&&isLeaf)
    	{
    		printf("A path is found: ");
    		std::vector<int>::iterator iter = path.begin();
    		for (; iter != path.end(); ++iter)
    		{
    			printf("%d\t", *iter);
    		}
    		printf("\n");
    	}
    	if (root->_left != NULL)
    	{
    		FindPath(root->_left, exp, path, curr);
    	}
    	if (root->_right != NULL)
    	{
    		FindPath(root->_right, exp, path, curr);
    	}
    	curr -= root->_value; path.pop_back();
    }

[Center]: /images/20220613/3a6f2156146b469dae8679da0a6a7f9c.png
[Center 1]: /images/20220613/7fc2b2dd348641b292909729a6c11144.png