[Accepted] By using postorder traversal


  • 43
    S

    In the postorder traversal, the node will be removed from the stack only when the right sub-tree has been visited.so the path will be stored in the stack. we can keep check the SUM, the length from root to leaf node.
    at leaf node, if SUM == sum, OK, return true. After postorder traversal, return false.

    I have compared this solution with recursion solutions. In the leetcode OJ, the run time of two solutions is very near.

    below is my iterator code.

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

  • 0
    C

    Hi SJames,
    Can you explain how the "pre" variable works. I have studied for a while, but don't really get it.
    Thanks,


  • 0
    S

    OK. The post order of the example tree is [7, 2, 11, 4, 13, 1, 4, 8, 5], when cur is 2, pre is 7. cur is 11, pre is 2. So, pre is just in front of cur. You may first simulate how the post order going in paper and draw every route.


  • 0
    C

    Got it. Thanks


  • 9
    A

    I think DFS is pretty simple and easy to code, just reduce the sum as you go down the tree and check the sum when you reach a leaf

        bool hasPathSum(TreeNode *root, int sum)
        {
            // empty node reached
    	    if (root == NULL)
                return false;
    
            // a leaf is reached
    	    if (root->left == NULL && root->right == NULL)
    	        return (root->val == sum);
    
            // send the value of (sum - currentNode) to the left and the right
    	    return hasPathSum(root->left, sum-(root->val)) ||
                        hasPathSum(root->right, sum-(root->val));
        }
    

  • 0
    I
    This post is deleted!

  • 0

    Hi, hatemfaheem. Your code is concise and easy. However, sometimes an interviewer may ask you to do the same thing without using recursion...


  • 0

    I like this idea. But why do you call it postorder traversal instead of preorder traversal? Could you please explain the reason here? Thanks.


  • 0
    S

    Here is the wiki link about preorder, inorder and postorder traversal. https://en.wikipedia.org/wiki/Tree_traversal

    I visit each node in post order. So, it is a postorder traversal solution.


  • 0
    R

    Really genius idea. Can you please elaborate more about this line
    cur->right && pre != cur->right about the post order traversal? How did you come out this way of traversal?


  • 3
    S

    pre is always the previous node has been visited. In post order traversal, If it's right child has been vistited, pre must be it's right child. cur->right && pre != cur->right means that cur has a right child, but has not been visited. So we should post order the right child tree.

    suppose you have a tree like this:

               a 
            /     \ 
          b       c
        /    \
       d    e
    

    If cur = b, pre = e. So, we have visited the right tree e.
    If cur = a, pre = b. So, we have not vistied the right tree c.

    I wish it helps.


  • 0
    A

    You said “In the leetcode OJ, the run time of two solutions is very near.”
    In your iterator code the time costs 15ms,but only cost 12ms in recursion code.How do you think in this solution why iterator method costs longer time than recursion way.Thx!


  • 0
    S

    In my test, just now. Both need 12ms.


  • 0
    A

    Oh,I find that the LeetCode runtime may changed in different time.
    Now the time is 12ms while 15ms last night.Thank you!


  • 0
    R

    Good solution, especially keeping a track of the pre, postorder solution is the most intuitive solution. A preorder traversal could also work. Thanks!


  • 0
    M

    I feel like it's an inorder traversal, since you pop the left node off the stack first, then the node itself, then the right node.

    For the example, pop 7 off first, then 11, then 2...

    Can you explain why you said post-order instead of inorder? @SJames


  • 0
    B

    @UpTheHell Add value to sum in preorder , minus value from sum in postorder. It's like backtracking algorithm. If you use inorder or preorder traversal, how do you backtrack and minus parent value if you already pop out parent node from stack? But in postorder traversal, the parent node be removed only when its left subtree and right subtree have been visited.


  • 0

    Nice solution. Although this iterative PostOrder traversal is not implemented the way I am most familiar with, the code itself is very elegant.


Log in to reply
 

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