112. 路径总和

112. 路径总和

题目链接：112. 路径总和

代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
 //思路：非递归后序遍历
class Solution {
   
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
   
        vector<TreeNode*> sta;//用数组模拟栈
        TreeNode* p=root;
        TreeNode* r=nullptr;

        while(p||!sta.empty())
        {
   
            if(p)//保存，一直找其左子树
            {
   
                sta.push_back(p);
                p=p->left;
            }
            else
            {
   
                p=sta[sta.size()-1];
                if(p->right&&p->right!=r)
                {
   
                    p=p->right;
                }
                else
                {
   
                    p=sta[sta.size()-1];
                    
                    //p为叶子节点，此时数组中保存的都是根到该叶子节点的节点
                    if(p&&p->left==nullptr&&p->right==nullptr)
                    {
   
                        int sum=0;
                        for(int i=0;i<sta.size();i++)
                        {
   
                            sum+=sta[i]->val;
                        }    

                        //找到了这样的路径，直接返回即可
                        if(sum==targetSum)
                            return true;
                    }

                    sta.pop_back();//弹出栈顶元素
                    r=p;
                    p=nullptr;
                }
            }
        }
        //遍历了所有根到叶子结点的路径，没找到
        return false;
    }
};