剑指offer_面试题25_二叉树中和为某一值的路径

末蓝、 2022-08-04 04:17 87阅读 0赞

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

举例：

/ \\

5 12

/ \\

4 7

**过程分析：**输入如上二叉树 和 整数位22

从头结点 10 开始 =====》遍历左结点 5====》判断是否是叶结点 ===否===》继续遍历左结点4=====》判断是否是叶结点 ===是===》计算这条路径数据和，并判断是否等于输入整数=====》否======》返回上一节点，遍历结点5的右结点7=====》判断是否是叶结点====》是，计算数据和，且等于输入整数=====》打印这条路径=====》返回到结点10===》再次遍历右子树12======》判断是否业叶结点====》是=====》计算数据和，且等于输入整数=====》打印=====》结束

**规律总结：**

1、路径保存，依照过程的分析，可以用 vector 来保存，往下遍历的时候，在尾部插入元素；往上回溯的时候，删除尾部元素；并且支持遍历打印路径

2、通过过程分析，可以使用递归，如果左子树不空，递归左子树；如果右子树不空，递归右子树

3、当遍历到叶结点，且数据和等于输入整数，打印

**算法如下：**

#include "TreeNode.h"
    #include <vector>
    
    using namespace std;
    
    void find_path(TreeNode *pRoot, vector<int>& path, int currentSum, int elem);
    
    void FindPath(TreeNode *pRoot,int elem)
    {
        if(NULL == pRoot)
            return;
    
        vector<int> path;       /**这里不应将头结点入队*/
        int currentSum = 0;     /*路径结点数据和*/
    
        find_path(pRoot, path, currentSum, elem);
    }
    
    void find_path(TreeNode *pRoot, vector<int>& path, int currentSum, int elem)
    {
        /** 这里确实多余，因为在传递进来之前会检查这个指针是否为空
        if(NULL == pRoot)
            return;
        */
    
        /**刚加入一个节点，因此路径元素和加上这个值*/
        currentSum += pRoot->m_pValue;
        path.push_back(pRoot->m_pValue);
    
        /**如果是叶结点，并且路径结点元素的和等于elem，那么打印这条路径*/
        if(currentSum == elem && pRoot->lchild == NULL && pRoot->rchild == NULL)
        {
            cout << "A path is found: ";
            for(vector<int>::size_type i = 0; i < path.size(); i++)
                cout << path[i] << ' ';
            cout << endl;
        }
    
        /**如果左右孩子不为空*/
        if(pRoot->lchild)
            find_path(pRoot->lchild, path, currentSum, elem);
        if(pRoot->rchild)
            find_path(pRoot->rchild, path, currentSum, elem);
    
        path.pop_back();   /**返回上一个结点之前，这条路径上的尾结点需要删除*/
    }
    
    void test1()
    {
        TreeNode *p1 = create_Treenode(10);
        TreeNode *p2 = create_Treenode(5);
        TreeNode *p3 = create_Treenode(12);
        TreeNode *p4 = create_Treenode(4);
        TreeNode *p5 = create_Treenode(7);
    
        connect_Treenode(p1,p2,p3);
        connect_Treenode(p2,p4,p5);
    
        FindPath(p1,22);
    }
    
    int main()
    {
        test1();
        return 0;
    }

**总结：**

**分析过程，总结规律，算法逃不出总结的规律。**

/\* 点滴积累，我的一小步 \*/