How to do non-recursive preorder traversal without two stacks(or vectors)?


  • 2
    I

    I only come up with the following code, which requires extra space to store the sumup value up to each node. Quite obvious it's too space consuming. Any idea on how to eliminating the stack storing the summed up value without munging the code up ?

    Inside the code, "st" is used to store TreeNodes*, and "stval" is used to store the sum of the vals along the path from the root to the current node. Other code should be quite self explanatory.

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

  • 0
    D

    you can try simple recursive approach ..

    class Solution {
    public:
     bool hasPathSum(TreeNode *root, int sum) {
         if(root == NULL)return false;
         return get(root,sum);
     }
    bool get(TreeNode *root,int sum){
        if(root == NULL)return false;
        else if(root->left == NULL && root->right == NULL){
               if(sum-root->val == 0)return true;
        }
        if(get(root->left,sum-root->val) || get(root->right,sum-root->val)){
            return true;
        }
        return false;
    }
    };

  • 0
    T

    I think the extra space complexity is just O(h) instead of O(n), so actually it's not that big.


  • 4
    K

    I think you can't avoid 2 stacks with BFS/DFS based method since you need 1 stack for traversal and 1 stack for either sum info or parent info. BFS/DFS can't trace parent info. Unless someone has cleverer method.

    A trick can be play here is saving current sum in the tree. I have this passed test:

    class Solution {
    public:
        bool hasPathSum(TreeNode *root, int sum) {
            if (!root)
                return false;
            stack<TreeNode*> mystack;
            mystack.push(NULL);
            TreeNode *p = root;
            p->val = sum - p->val;
            while (p) {
                if (!p->left && !p->right && !p->val)
                    return true;
                if (p->right) {
                    p->right->val = p->val - p->right->val;
                    mystack.push(p->right);
                }
                if (p->left) {
                    p->left->val = p->val - p->left->val;
                    p = p->left;
                }
                else {
                    p = mystack.top();
                    mystack.pop();
                }
            }
            return false;
        }
    };

  • 0
    I

    "BFS/DFS can't trace parent info. Unless someone has cleverer method.". Exactly, that's what bothered me. PS, nice trick.


  • 0
    A

    A queue do the work

    import java.util.*;

    public class Solution {
    public static boolean isMirror(TreeNode tree1, TreeNode tree2){
    if(tree1 == null && tree2 == null) return true;
    if(tree1 == null || tree2 == null) return false; //considering both == null returned true

    if(tree1.val != tree2.val) return false;
    
    if(!Solution.isMirror(tree1.left, tree2.right)) return false;
    if(!Solution.isMirror(tree1.right, tree2.left)) return false;
    
    return true;
    

    }

    public static boolean isMirrorIt(TreeNode tree1, TreeNode tree2){
    if(tree1 == tree2) return true;
    if(tree1 == null || tree2 == null) return false; //considering both == null returned true

    LinkedList<TreeNode> Queue1 = new LinkedList<TreeNode>();
    LinkedList<TreeNode> Queue2 = new LinkedList<TreeNode>();
    Queue1.addLast(tree1);
    Queue2.addLast(tree2);
    
    // invariant: both queues have the same number of elements (not null)
    while(!Queue1.isEmpty()){
      TreeNode node1 = Queue1.removeFirst();
      TreeNode node2 = Queue2.removeFirst();
    
      if(node1.val != node2.val)
        return false;
    
      if(  (node1.left == null && node2.right != null)
         ||(node1.left != null && node2.right == null)
         ||(node1.right == null && node2.left != null)
         ||(node1.right != null && node2.left == null) )
        return false;
      else{
        if(node1.left != null){
          Queue1.addLast(node1.left);
          Queue2.addLast(node2.right);
        }
        if(node1.right != null){
          Queue1.addLast(node1.right);
          Queue2.addLast(node2.left);
        }
      }
    }
    
    return true;
    

    }

    public static boolean isSymmetric(TreeNode root) {
    if(root == null) return true;
    return (Solution.isMirror(root.left, root.right));
    }
    }


  • 0
    A

    A queue do the work

    public class Solution {
      public static boolean isMirror(TreeNode tree1, TreeNode tree2){
        if(tree1 == null && tree2 == null) return true;
        if(tree1 == null || tree2 == null) return false; //considering both == null returned true
    
        if(tree1.val != tree2.val) return false;
    
        if(!Solution.isMirror(tree1.left, tree2.right)) return false;
        if(!Solution.isMirror(tree1.right, tree2.left)) return false;
    
        return true;
      }
    
      public static boolean isMirrorIt(TreeNode tree1, TreeNode tree2){
        if(tree1 == tree2) return true;
        if(tree1 == null || tree2 == null) return false; //considering both == null returned true
    
        LinkedList<TreeNode> Queue1 = new LinkedList<TreeNode>();
        LinkedList<TreeNode> Queue2 = new LinkedList<TreeNode>();
        Queue1.addLast(tree1);
        Queue2.addLast(tree2);
    
        // invariant: both queues have the same number of elements (not null)
        while(!Queue1.isEmpty()){
          TreeNode node1 = Queue1.removeFirst();
          TreeNode node2 = Queue2.removeFirst();
    
          if(node1.val != node2.val)
            return false;
    
          if(  (node1.left == null && node2.right != null)
             ||(node1.left != null && node2.right == null)
             ||(node1.right == null && node2.left != null)
             ||(node1.right != null && node2.left == null) )
            return false;
          else{
            if(node1.left != null){
              Queue1.addLast(node1.left);
              Queue2.addLast(node2.right);
            }
            if(node1.right != null){
              Queue1.addLast(node1.right);
              Queue2.addLast(node2.left);
            }
          }
        }
    
        return true;
      }
    
      public static boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return (Solution.isMirror(root.left, root.right));
      }
    }

  • 0
    M
    This post is deleted!

  • 0
    L

    It is a nice trick to solve the problem. But somehow the trick alternates/destroys the original tree afterwards.


Log in to reply
 

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