leetcode: path sum

这个问题其实很简单，DFS的基础，所以我写了4个版本。第一个是递归，其实效率在4个里面算很好的，递归真的是简洁而优雅。

1
2
3
4
5
6
7
8
9
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (!root) return false;
        if (!root->left && !root->right) 
            return root->val == sum;

        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
	    }
	};

第二个非递归版本，用sp模拟栈，accessed记录访问过的节点。

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
class Solution2 {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (!root) return false;

        std::vector<TreeNode*> sp;
        unordered_map<TreeNode*, bool> accessed;

        sp.push_back(root);
        int len = 0;
        while (sp.size()) {    
            auto* np = sp.back();
            if (np->left && !accessed[np->left]) {
                len += np->val;                        
                sp.push_back(np->left);
            } else if (np->right && !accessed[np->right]) {
                len += np->val;                                        
                sp.push_back(np->right);
            } else {
                if (!np->left && !np->right)
                    if (len + np->val == sum) return true;
                accessed[np] = true;
                sp.pop_back();
                if (sp.size()) len -= sp.back()->val;
            }
        }

        return false;
    }
};

后面两个比较有意思，Solution3是一个intrusive版本，它在下降过程中修改子节点的val值，使得每个节点保存从根节点到达的路径的sum。这样，当遇到叶子节点时就知道这条路径的sum大小。

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
class Solution3 {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (!root) return false;

        std::vector<TreeNode*> sp;
        sp.push_back(root);
        while (sp.size()) {    
            auto* np = sp.back();
            sp.pop_back();

            if (!np->left && !np->right) {                
                if (np->val == sum) return true;
            }

            if (np->left) {
                np->left->val += np->val;                        
                sp.push_back(np->left);
            }
            if (np->right) {
                np->right->val += np->val;                                        
                sp.push_back(np->right);
            }
        }

        return false;
    }
};

第四个版本比较有意思，基础是morris遍历，所用得技巧跟第三版本比较类似，就是在下降过程中修改节点的val值，保存路径的sum大小。关键就是在哪几个地方做这个事情。看代码不如画图，画张图就清楚了。代码里的注释解释了一个问题，就是在找到一个解时不能直接return true。大概是leetcode提交环境的问题，因为morris遍历修改了每个节点的左子树的最右节点的right指向，leetcode希望树结构保持不变。

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
class Solution4 {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (!root) return false;

        bool ret = false;
        TreeNode* nd = root;
        while (nd) {
            if (!nd->left) {
                //NOTE: can not write `return true` here. since morris traversion modified
                //struture of tree, we need to run over to make sure all changes restored.
                //because of this, this may not as fast as primitive solution.
                if (!nd->right && nd->val == sum) ret = true;
                if (nd->right) nd->right->val += nd->val;                
                nd = nd->right;
            } else {
                auto* l = nd->left;
                while (l->right && l->right != nd) l = l->right;
                if (l->right == nd) {
                    if (!l->left && l->val == sum) ret = true;                                                                        
                    nd = nd->right;
                    l->right = nullptr;
                } else {
                    nd->left->val += nd->val;                    
                    if (nd->right) nd->right->val += nd->val;                    
                    l->right = nd;
                    nd = nd->left;
                }
            }
        }

        return ret;
    }
};