C++ non-recursive solution


  • -3
    L

    use post order traversal.
    1.1 Create an empty stack
    2.1 Do following while root is not NULL
    a) Push root's right child and then root to stack.
    b) Set root as root's left child.
    2.2 Pop an item from stack and set it as root.
    a) If the popped item has a right child and the right child
    is at top of stack, then remove the right child from stack,
    push the root back and set root as root's right child.
    b) Else print root's data and set root as NULL.
    2.3 Repeat steps 2.1 and 2.2 while stack is not empty.
    see the detailed explanation for the post order traversal here
    http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/

    class Solution {
    public:
    bool hasPathSum(TreeNode* root, int sum) {
    stack<TreeNode*> st;
    TreeNode* itr = root;
    while(itr != NULL || !st.empty()){
    while(itr != NULL){
    if(itr->right != NULL)
    st.push(itr->right);
    st.push(itr);
    sum -= itr->val;
    itr = itr->left;
    }
    TreeNode* temp = st.top();
    st.pop();
    if(temp->left == NULL && temp->right == NULL && sum == 0)
    return true;
    if(temp->right && !st.empty() && temp->right == st.top()){
    itr = st.top();
    st.pop();
    st.push(temp);
    }else{
    sum += temp->val;

            }
        }
        return false;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.