Sunday, September 10, 2017

112. Path Sum

https://leetcode.com/problems/path-sum/description/

Recursion
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        if(!root->left && !root->right && sum==root->val) return true;
        return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
    }
or,
    bool preOrder(TreeNode* node, int sum, int s) {
        s += node->val;
        if(!node->left && !node->right && s==sum) return true;
        return (node->left? preOrder(node->left, sum, s):false) ||
        (node->right? preOrder(node->right, sum, s):false);
    }
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        return preOrder(root, sum, 0);
    }
Iteration
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        stack<TreeNode*> st;
        stack<int> sm;
        st.push(root);
        sm.push(0);
        TreeNode* node;
        int sn = 0;
        while(!st.empty()) {
            node = st.top();
            st.pop();
            sn = sm.top() + node->val;
            sm.pop();
            if(!node->left && !node->right && sn==sum) return true;
            if(node->right) {st.push(node->right); sm.push(sn);}
            if(node->left) {st.push(node->left); sm.push(sn);}
        }
        return false;
    }

No comments:

Post a Comment