剑指offer第24题题解

    //剑指offer第24题：输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的 所有 路径。
    // 解法一：非递归算法：自己写的，用vector和stack进行实现,不需要子函数
    //这个是自己写出来的第一个关于二叉树的这么复杂的程序，后来看了别的大佬递归的算法，发现很简便，自己的程序还是太繁琐了，
    // 主要是各种边界条件判断的比较多，但是思路是这么个思路：后序遍历，即先从左开始，然后右，最后再去上面找刚开始存的别的右
//下面这个用来将size比较大的vector放在前面  但其实不放也能通过程序的测试
bool Comp(const vector<int> &a,const vector<int> &b);
bool 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);
        return path_sum;
    }