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

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */

#include <stack>
class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        stack<TreeNode*> Node;
        int tmpcnt = 0;
        // if(root!=nullptr&&root->val>sum)
        //     return false;
        while(root!=nullptr||!Node.empty()){
            while(root!=nullptr){
                Node.push(root);
                tmpcnt+=root->val;
                //cout<<"root"<<root->val<<" tmp:"<<tmpcnt<<endl;
                if(root->left!=nullptr)
                    root = root->left;
                else
                    root=root->right;
            }
            if(tmpcnt==sum)
                return true;
            root = Node.top();
            Node.pop();
            tmpcnt-=root->val;
            //cout<<"root"<<root->val<<" tmp:"<<tmpcnt<<endl;
            while(!Node.empty()&&(root == Node.top()->right||Node.top()->right==nullptr)){
                root = Node.top();
                Node.pop();
                tmpcnt-=root->val;
            }
            if(!Node.empty()&&root == Node.top()->left)
                root = Node.top()->right; 
            else
                root = nullptr;
        }
        return false;
    }
};

这个题我一开始就想直接用后序遍历的迭代方法的思路去做，结果把能出的bug基本都出了一遍，救命。。。

先写解题思路，再写出过的bug：

前面很常规，遇到一个结点就把这个结点的值加上，一直往左走，走到最后一个左节点，就往右走，这样25行的循环停止的时候一定走到了叶子结点。如果此时的总和是目标值，直接返回。如果不是，则需要开始回溯。目前的总和就是栈中结点的总和，栈中结点是包含叶子结点的。先把叶子结点弹出来，总和减去这个结点的值。然后需要考虑此时栈顶结点的所有到叶子结点的路径是不是都走完了，判断方法就是，此时的root是栈顶结点的右子树，或者栈顶结点没有右子树。只要满足这个条件，说明栈顶的结点也一定不在满足要求的路径中，也需要弹出。

直到找到路径还没探索完的一个栈顶结点，将root指针置为该栈顶结点的右子树。如果栈为空，则将root置为nullptr，使得循环结束。

出的bug：

1 没有考虑结点有可能是复数，在遍历节点过程中加了一个条件，tmpcnt>sum就退出

2 死循环

死循环出现的原因是没有在栈空的时候把root置为nullptr，此时的root停在最后一个从栈里弹出的结点上，它会重新进入25的循环，重新开始找它已经遍历过的点。

3 在非叶节点算出了符合要求的和，直接返回true

这个bug出现的原因是我在考虑当前栈顶元素的孩子是不是遍历完的条件是Node.top()->left是不是等于root，如果等于，我就认为没有遍历完，而将root置为Node.top()->right。这样就有可能出现Node.top()->right为空（也就是栈顶元素没有右孩子，所以栈顶元素已经遍历完了，而我以为没有遍历完），这样下次循环中，算法检测到root=nullptr，会将栈顶元素当作一个叶子节点，从而判断和是否为sum。而此时栈顶元素是有左子树，并非叶节点。因此会出现错误的答案。解决这个bug的方法就是将考察栈顶元素是否遍历完的条件加一个可能Node.top()->right==nullptr

总的来说，要时刻记得算法认为的root=nullptr只有可能发生在栈顶元素是叶节点的时候，所以需要警惕其他时候不小心将root置空