剑指offer24题题解

剑指offer第24题：输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的 所有 路径。
这题做个记录，这道题感觉有点水平，而且是自己运用前几题中学到的知识然后自己写出了一个本题的非常复杂的解法。。。。也算是能通过测试用例，算是自己写出的第一个解法（代码中被注释的解法一），而且在看别的同学的解法过程中，学到了很多东西，在程序里注释了很多，比如二叉树的题一般都能用递归解法（比较简便）；当二叉树广义遍历时候，需要结束其他的数据结构，如stack；还学到了如何根据vector的size对其进行排序；还有静态函数和全局函数等等。。

#include<iostream>
#include<vector>
#include <stdlib.h>
#include <string.h>
#include<stack>
#include<queue>
#include<list>
#include <algorithm>
#include<array>
#include <numeric>
using namespace std;
// 注意：把这个Comp函数写到main外面  并且在class之前声明 才可以用！！！！！！！！！！！！（全局函数）
//不能写到class里面  不然sort函数调用不了这个comp函数！！！！！！！！！
//再次注意：可以把这个函数声明为static 静态函数  也能在类里调用！！！！！！！！（静态函数）
//bool Comp(const vector<int> &a,const vector<int> &b);

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};

class Solution {
public:

    // 剑指offer第24题：输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的 所有 路径。
    // 解法一：非递归算法：自己写的，用vector和stack进行实现,不需要子函数
    // 这个是自己写出来的第一个关于二叉树的这么复杂的程序，后来看了别的大佬递归的算法，发现很简便，自己的程序还是太繁琐了，
    // 主要是各种边界条件判断的比较多，但是思路是这么个思路：后序遍历，即先从左开始，然后右，最后再去上面找刚开始存的别的右
// 有个特别需要注意的点：即这个路径的尾节点必须是叶子节点，即它不能有左节点和右节点
//下面这个函数时为了满足题目要求：路径长的在前面  这个函数由于被调用了sort函数（在class里调用了sort函数）  所以需要为静态函数或者全局函数？？
    // bool static Comp(const vector<int> &a,const vector<int> &b) //声明为静态函数！！！！！！！！！！！才能在类里调用
    // {
    //     return a.size() > b.size();
    // }

    // vector<vector<int> > FindPath(TreeNode* root,int expectNumber) 
    // {
    //     vector<vector<int> > path_sum;
    //     if(root==NULL)
    //     {
    //         return path_sum;
    //     }
    //     //vector<int> vec1;
    //     vector<int> vec1;//这是用来存储可能会满足该整数的路径节点
    //     stack<TreeNode*> s1; //存储右节点，回溯的时候有迹可寻，利用了stack的先进先出的特性
    //     stack<int> flag; //这个是标志位，即root->left无效要换到root->right右侧时，vec1应该回溯到哪个父节点开始新的路径，即vec1里的数应该去掉多少个合适
    //     int sum = 0;//路径和
    //     while(root)
    //     {
    //         int val1 = root->val;
    //         vec1.push_back(val1);
    //         sum = sum+val1;
    //         if(sum==expectNumber)
    //         {
    //     //注意，当路径和等于该整数时，不能就存储进去，还得进一步判断它是否是叶子节点，即保证它的left和right都为NULL
    //             if(root->left==NULL && root->right==NULL)
    //             {

    //                 path_sum.push_back(vec1);
    //                 //注意：当存储了一条路径之后还得继续判断是否有右边的路径和满足这个整数
    //                 if(!s1.empty())
    //                 {
    //                     root = s1.top();
    //                     s1.pop();
    //                     //这里就是回溯到这个top出来的右节点对应的父节点的值，把没用的都从vec1中删去，同时从sum中减去
    //                     while(flag.top()!=vec1[vec1.size()-1])
    //                     {                       
    //                         sum  = sum-vec1[vec1.size()-1];
    //                         vec1.pop_back();
    //                     }
    //                     flag.pop();                    

    //                 }
    //                 else
    //                 {
    //                     break;    //该加的break必须得加 不然跳不出这个循环
    //                 }
    //             }
    //             else //如果该节点下面还有左孩子或右孩子，那只能直接跳过，因为到叶子节点肯定已经大于这个整数了
    //             {
    //                 if(!s1.empty())
    //                 {
    //                     root = s1.top();
    //                     s1.pop();
    //                     while(flag.top()!=vec1[vec1.size()-1])
    //                     {                       
    //                         sum  = sum-vec1[vec1.size()-1];
    //                         vec1.pop_back();
    //                     }
    //                     flag.pop();                    

    //                 }
    //                 else
    //                 {
    //                     break;    //该加的break必须得加 不然跳不出这个循环
    //                 }
    //             }



    //         }
    //         else if(sum>expectNumber) //如果到这个节点已经大于该整数了
    //         {
    //             if(!s1.empty())
    //             {
    //                 root = s1.top();
    //                 s1.pop();
    //                 while(flag.top()!=vec1[vec1.size()-1])
    //                 {                       
    //                     sum  = sum-vec1[vec1.size()-1];
    //                     vec1.pop_back();
    //                 }
    //                 flag.pop();                    

    //             }
    //             else
    //             {
    //                 break;
    //             }

    //         }
    //         else//如果到这个节点，小于该整数，那继续往左节点走或往右节点走
    //         {
    //             if(root->left)
    //             {
    //                 //root = root->left;
    //                 if(root->right)
    //                 {
    //                     s1.push(root->right);
    //                     flag.push(val1);
    //                 }
    //                 root = root->left;
    //             }
    //             else if(root->right)
    //             {
    //                 root = root->right;

    //             }
    //             else
    //             {
    //                 if(!s1.empty())
    //                 {
    //                     root = s1.top();
    //                     s1.pop();
    //                     while(flag.top()!=vec1[vec1.size()-1])
    //                     {                       
    //                         sum  = sum-vec1[vec1.size()-1];
    //                     vec1.pop_back();
    //                     }
    //                     flag.pop();                    

    //                 }
    //                 else
    //                 {
    //                     break;
    //                 }


    //             }

    //         }

    //     }
    //     sort(path_sum.begin(),path_sum.end(),Comp); //此时的comp需要为全局函数或者为静态函数才能在这里直接调用
    //     return path_sum;
    // }
    //！！！！！！！！！！！进行数组长度大小排序的另一种方法，不适用sort封装好的函数，利用insert插入这个操作，
    //如果大于前面的数组size则插到它前面
    // if (paths.size() == 0)
    // {
    //     paths.push_back(temp_path);
    // }

    // else
    // {
        //int flag = 0;
    //     for (int idx = 0; idx < paths.size(); idx++)
    //     {
    //         if (temp_path.size()>paths[idx].size())
    //         {
    //             paths.insert(paths.begin() + idx, temp_path);
    //             break;
    //         }
    //     }
    //     需要加个标志位
    //     if(flag==0)
    //     {
    //        paths.push_back(temp_path);
    //     }
    // }


    // 找路径解法二：牛客上大佬写的，递归算法，非常简洁
    vector<vector<int> > path_sum;
    vector<int> path;
    vector<vector<int> > FindPath(TreeNode* root,int expectNumber)
    {
        if(root==NULL)
        {
            return path_sum;
        }
         find(root,expectNumber);
         return path_sum;
    }
     // 注意：把path_sum定义为了类的成员变量，相当于是全局变量，不会因为return而乱
     //这也是为什么需要创建一个子函数find的原因，虽然俩函数的参数一样，但确实需要这个子函数
    void find(TreeNode* root,int sum) //这个sum表示剩下的结点值应该是多少能满足条件 
    {                           // sum是差值  而我一般的思路是把它们都加起来。。还是有差距的
        path.push_back(root->val);
        if(!root->left && !root->right && root->val==sum)
        {
            if(path_sum.size()==0) //这部分实现size大（路径长的）在前
            {
                path_sum.push_back(path);
            }
            else
            {
                int flag = 0;
                for(int i=0;i<path_sum.size();i++)
                {
                    if(path.size()>path_sum[i].size())
                    {
                        path_sum.insert(path_sum.begin()+i,path);
                        flag = 1;
                        break;
                    }

                }
                if(flag==0)
                {
                    path_sum.push_back(path);
                }
            }    
        }
        else
        {
            if(root->left)
            {
                find(root->left,sum-root->val);
            }
            if(root->right)
            {
                find(root->right,sum-root->val);
            }

        }
        path.pop_back();
    }

    //根据前序和中序重建二叉树
    TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin)
    {
    if (pre.empty() || vin.empty())
        return NULL;
    int count = 0;
    for (int i = 0; i < vin.size(); ++i)
    {
        if (pre[0] == vin[i])
            count++;
    }
    if (count != 1)
        return NULL;

    vector<int> pre_left, pre_right, vin_left, vin_right;
    int val = pre[0];
    TreeNode* root = new TreeNode(val);
    int pos;

    for (pos = 0; pos < vin.size(); ++pos)
    {
        if (vin[pos] == val)
            break;
    }

    for (int i = 0; i < vin.size(); ++i){

        if (i < pos){
            vin_left.push_back(vin[i]);
            pre_left.push_back(pre[i + 1]);
        }
        else if (i > pos)
        {
            vin_right.push_back(vin[i]);
            pre_right.push_back(pre[i]);
        }
    }
    root->left = reConstructBinaryTree(pre_left, vin_left);
    root->right = reConstructBinaryTree(pre_right, vin_right);
    return root;
    }
};
// bool Comp(const vector<int> &a,const vector<int> &b);
int main(){

    Solution *s1 = new Solution;
    TreeNode *r;
    vector<int> vec1,vec2,vec3;
    vec1 = {1,2,4,7,3,5,6,8}; //前序遍历
    vec2 = {4,7,2,1,5,3,8,6}; //中序遍历
    vec3 = {7,4,2,5,8,6,3,1}; //后序遍历
    r = s1->reConstructBinaryTree(vec1,vec2);
    vector<vector<int> > result;
    result = s1->FindPath(r,9);
    for(int i=0;i<result.size();i++)
    {
        for(int j=0;j<result[i].size();j++)
        {
            cout<<result[i][j]<<endl;
        }
    }
    //以下程序实验sort这个函数
    // vector<vector<int> > vec_2d;
    // vector<int> vec5,vec6;
    // vec5 = {1,2,4,7,3,5,6}; 
    // vec6 = {4,7,2,1,5,3,8,6}; 
    // vec_2d.push_back(vec5);
    // //vec_2d.push_back(vec6);
    // sort(vec_2d.begin(),vec_2d.end(),Comp);

    return 0;
}
// bool Comp(const vector<int> &a,const vector<int> &b) 
// {
//     return a.size() > b.size();
// }