剑指Offer25二叉树中和为某一值的路径

本文主要是介绍剑指Offer25二叉树中和为某一值的路径，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

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

分析：

看到这个题首先想到的这是一个深搜的题目。

从根结点开始遍历，当遍历到叶子结点时，记录下这一路经中的和，如果和给定的值相等就是要找的路径，然后输出路径（用一个栈来记录路径），如果不相等就回溯，同时记录路径的栈也把最后进栈的数字抛出。

用深搜肯定是用递归来实现最简单，下面看代码：

void FindPath(BinaryTreeNode * Node,int sum,std::vector<int>path,int count)
{count += Node->m_nValue;path.push_back(Node->m_nValue);bool isLeaf = (Node->m_pLeft==NULL && Node->m_pRight==NULL);if(sum == count && isLeaf){cout<<"找到了"<<endl;std::vector<int>::iterator iter = path.begin();for(;iter != path.end();iter++)printf("%d\t",*iter);cout<<endl;}if(Node->m_pLeft)FindPath(Node->m_pLeft,sum,path,count);if(Node->m_pRight)FindPath(Node->m_pRight,sum,path,count);path.pop_back();
}
void FindPath(BinaryTreeNode * RootNode,int sum)
{if(RootNode == NULL )return ;std::vector<int> path;int count = 0;FindPath(RootNode,sum,path,count);
}

这篇关于剑指Offer25二叉树中和为某一值的路径的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---