题解 | #二叉树中和为某一值的路径(三)#

/**
*当root为空时，此时去访问root->left root->right一定会报错错误 
*请注意
*/


/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
#include <cstddef>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return int整型
     */
    int ans=0;
    void dfs(TreeNode* root,int tmp_sum,const int key){
         if(root == nullptr){
            return;
        }
        //cout<<root->val<<"  "<<tmp_sum<<endl;
        tmp_sum +=root->val;
        //cout<<root->val<<"  "<<key<<endl;

        if(tmp_sum == key){
            cout<<"???"<<endl;
            ans++;
            //return;
        }


        dfs(root->left,tmp_sum,key);
        dfs(root->right,tmp_sum,key);
        
    }
    void thread_order(TreeNode* root, int sum){
        // cout<<(root==nullptr)<<" "<<(root->left==nullptr)<<"  "<<(root->right==nullptr)<<endl;
        if(root ==nullptr) return;
        if(root != nullptr){
            dfs(root,0,sum);
        }
        if(root->left!=nullptr){
            thread_order(root->left,sum);
        }
        if(root->right!=nullptr){
            thread_order(root->right,sum);
        }
        return;
    }

    int FindPath(TreeNode* root, int sum) {
        // write code here

        stack<TreeNode*> st;
        
        thread_order(root,sum);
        
        // if(root)
        // st.push(root);

        // while(!st.empty()){
        //     auto head = st.top();
        //     // cout<<head->val<<endl;
        //     dfs(head,0,sum);

        //     st.pop();
        //     if(head->right)
        //     st.push(head->right);
        //     if(head->left)
        //     st.push(head->left);

        // }


        return ans;
    }
};