bool hasPathSum(struct TreeNode* root, int sum ) {
    // write code here
    int nowsum = 0;
    int i = 0;
    struct TreeNode** arr = (struct TreeNode**)malloc(sizeof(
                                struct TreeNode*) * 100);
    if (root != NULL) {
        i++;
        arr[i] = root;
        nowsum += arr[i]->val;
    }

    while (i > 0) {
        while (arr[i]->left != NULL && arr[i]->left->val != 1001) {
            i++;//入栈
            arr[i] = arr[i - 1]->left;
            nowsum += arr[i]->val;
        }

        if (arr[i]->right == NULL) {
            if (arr[i]->left == NULL && nowsum == sum)
                return true;
            nowsum -= arr[i]->val;
            arr[i]->val = 1001;//表示已访问过
            i--;//出栈
            if (i < 1)
                break;
        } else {
            if (arr[i]->right->val != 1001) {
                i++;
                arr[i] = arr[i - 1]->right;
                nowsum += arr[i]->val;
            } else {
                nowsum -= arr[i]->val;
                arr[i]->val = 1001;
                i--;
            }
        }
    }

    return false;
}