二叉树根节点到指定节点的路径

青旅半醒 2022-08-26 14:20 176阅读 0赞

题目描述：给定一棵二叉树和二叉树中一个节点，输出根节点到指定节点间的路径。

10     
  　　　　/ \\     
 　　　　5  12     
  　　　 / \\      
  　　  4    7

指定节点7，那么输出路径应该是10-5-7。

分析与解法：

这个题目是在我做过蛮多二叉树的题目之后总结的一道题目。发现很多题目都可以抽象出来这个题目。其实二叉树本来就是最典型的递归数据结构，只要完全掌握三种遍历方法，一切题目都是浮云。

这道题目和博客[http://blog.csdn.net/getnextwindow/article/details/23326843][http_blog.csdn.net_getnextwindow_article_details_23326843]输出所有满足条件的路径颇为相似。只不过这道题目只要找到目的路径就要尽快返回，不要再遍历下去。不多解释，我会在代码中给予注释。

代码如下：

**\[cpp\]**  [view plain][] [copy][view plain] [print][view plain] [?][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **bool** specialPath(Node \*pRoot,Node \*pNode,vector<**int**> &v)  
2.  \{  
3.      **if**(pRoot==NULL)  
4.      \{  
5.          **return** **false**;  
6.      \}  
7.      v.push\_back(pRoot->m\_value);  
8.      **bool** found=**false**;  
9.      **if**(pRoot==pNode)//还是比较指针稳妥，节点值有可能重复  
10.     \{  
11.         found=**true**;  
12.         **for**(**int** i=0;i<v.size();i++)  
13.             cout<<v\[i\]<<" ";  
14.         cout<<endl;  
15.     \}  
16.     **if**(!found && pRoot->m\_pLeft)  
17.     \{  
18.         found=specialPath(pRoot->m\_pLeft,pNode,v);  
19.     \}  
20.   
21.     //一旦左子树中找到节点，就不需要再遍历右子树  
22.     **if**(!found && pRoot->m\_pRight)  
23.     \{  
24.         found=specialPath(pRoot->m\_pRight,pNode,v);  
25.     \}  
26.    //pop\_back函数只删除最后一个元素
27.     v.pop\_back();  
28.     //不要忘记这个返回found  
29.     **return** found;  
30. \}

[http_blog.csdn.net_getnextwindow_article_details_23326843]: http://blog.csdn.net/getnextwindow/article/details/23326843
[view plain]: http://blog.csdn.net/GetNextWindow/article/details/23332265#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/284315
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/284315/fork