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

//深度优先遍历非递归方法
//深度优先遍历和前序基本没什么区别，唯一的区别就是前序遍历讲究顺序
//深度优先遍历不讲究顺序，所以深度优先非递归直接照搬前序遍历非递归即可
/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    bool hasPathSum(TreeNode* root, int sum) {
        // write code here
        if(root==NULL)
            return false;
        stack<TreeNode*> nodeStack;//专门用来存储节点的栈
        stack<int> dataStack;//专门用来存储对应的节点值得栈
        nodeStack.push(root);
        dataStack.push(root->val);
        while(!nodeStack.empty()&&!dataStack.empty()){//当栈不为空时
            TreeNode*node=nodeStack.top();
            nodeStack.pop();
            int value=dataStack.top();
            dataStack.pop();
            if(node->right!=NULL){
                nodeStack.push(node->right);
                dataStack.push(value+node->right->val);
            }
            if(node->left!=NULL){
                nodeStack.push(node->left);
                dataStack.push(value+node->left->val);
            }
            if(node->left==NULL&&node->right==NULL&&value==sum)
                return true;
        }
        return false;
    }
};