[leetcode_112]Path Sum

给定一个二叉树，跟定一个数字sum，从根开始到各叶节点的路径依次求和，请问是否有叶节点的值满足和sum相等。
这个题，其实BFS然后依次枚举就行，但是注意边界，首先是叶节点，然后考虑root无子节点和root为空的情况。
附上代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55


class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        TreeNode ** seq = new TreeNode*[10000];
        TreeNode ** rseq = new TreeNode*[10000];
        if(root == NULL)
            return false;
        else
        {
            if(root->left == NULL && root->right == NULL)
            {
                if(root->val == sum)
                    return true;
                else
                    return false;
            }
            int index = 0;
            seq[index++] = root;
            while(true)
            {
                int top = index;
                index = 0;
                for(int i = 0;i < top;i++)
                {
                    if(seq[i] != NULL)
                    {
                        if(seq[i]->left != NULL)
                        {
                            seq[i]->left->val += seq[i]->val;
                            rseq[index++] = seq[i]->left;
                            if(seq[i]->left->val == sum && seq[i]->left->left == NULL && seq[i]->left->right == NULL)
                                return true;
                        }
                        if(seq[i]->right != NULL)
                        {
                            seq[i]->right->val += seq[i]->val;
                            rseq[index++] = seq[i]->right;
                            if(seq[i]->right->val == sum && seq[i]->right->left == NULL && seq[i]->right->right == NULL)
                                return true;
                        }
                    }
                }
                if(index == 0)
                    break;
                for(int i = 0;i < index;i++)
                {
                    seq[i] = rseq[i];
                }
            }
            return false;
        }
    }
};